Editorial for Bedao Regular Contest 07 - DEADLINE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1-2:

Để qua ~40%~ test đầu các bạn có thể xét từng ~k~ rồi xử lí độc lập như sau:

Sắp xếp ~k~ công việc đầu theo ~d_i~. Gọi ~S~ là tập heap_max lưu trữ các công việc chưa được làm Xét từng thời điểm ~d~ theo thứ tự giảm dần, đến ~d~ của việc nào thì ném việc đó vào tập ~S~. Sau khi ném xong thì chọn việc sẽ làm tại thời điểm ~d~ là một việc nào đó trong tập ~S~ (hiển nhiên là việc có p lớn nhất).

Subtask 3:

Ta sẽ tìm cách xây dựng mối liên kết giữa công việc ~k~ vào bài toán ~(k-1)~ công việc đã xét ở trước. Vậy, công việc ~k~ có 2 trường hợp thay đổi kết quả bài toán là :

~1)~ Công việc ~k~ có thêm vào tập các công việc được làm

~2)~ Công việc ~k~ thay thế một việc trong tập các công việc được làm

Để kiểm tra ~1)~ ta có điều kiện cần và đủ là (số lượng công việc có deadline bé hơn hoặc bằng ~i~) ~\leq i~ ~\{\forall~ ~i \in [1, \inf)\}~. Ta có thể xây dựng cây Segment Tree Max (Lazy Segment Tree), quản lí thời điểm và đặt trước cho phần tử thứ ~i~ là ~-i~. Từ đó, công việc ~k~ có thể thêm vào nếu phần tử lớn nhất trên cây SegTree bé hơn ~0~.

Còn nếu không đặt được thêm công việc ~k~ thì nó sẽ cố thay thế ~1~ việc nào đó trong tập được làm. Cách xử lí là ta sẽ thêm công việc ~k~ vào, lúc này trên cây SegTree sẽ có một số vị trí bằng ~1~ thì ta sẽ phải bắt buộc bỏ đi ~1~ công việc có p nhỏ nhất trong đoạn từ ~1~ đến vị trí đầu tiên mà bằng ~1~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.