Hướng dẫn cho AtCoder ABC128 E - Sửa đường
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Quét thời điểm xuất phát
Một người xuất phát lúc \(D\) tới vị trí \(X_i\) lúc \(D+X_i\). Các thời điểm đều nguyên, nên công trình chặn người này khi:
hay \(S_i-X_i\le D<T_i-X_i\). Mỗi công trình vì thế tạo một khoảng thời điểm xuất phát, đóng ở trái và mở ở phải, với chi phí là vị trí \(X_i\).
Sắp công trình theo đầu trái. Các câu hỏi \(D_j\) đã tăng dần. Trước khi hỏi tại \(D\), đưa mọi công trình có đầu trái không lớn hơn \(D\) vào heap ưu tiên \(X_i\) nhỏ nhất. Heap lưu cả đầu phải; liên tục bỏ phần tử đầu nếu đầu phải không lớn hơn \(D\). Công trình còn lại ở đầu heap là vị trí bị chặn đầu tiên. Nếu heap rỗng, đáp án là \(-1\).
Vì sao có thể xóa chậm trong heap?
Công trình hết hiệu lực nhưng còn ở sâu trong heap không quyết định đáp án. Khi nó lên đầu, vòng lặp sẽ bỏ nó. Sau vòng bỏ, phần tử đầu còn hiệu lực và có vị trí nhỏ nhất trong mọi công trình hiệu lực đã được thêm. Mọi công trình có thể chặn người này đều đã được thêm vì đầu trái của chúng không lớn hơn \(D\).
Mỗi công trình vào và ra heap nhiều nhất một lần. Thời gian là \(O(N\log N+Q\log N)\), bộ nhớ \(O(N)\) ngoài dữ liệu câu hỏi. Các đầu mút sau phép trừ có thể âm; không được ép chúng về \(0\) hay dùng số không dấu.
Bình luận