Editorial for Bedao Regular Contest 12 - FA


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

Trong tối đa ~t~ giây, người thứ ~i~ ở vị trí ~(x_i, y_i)~ sẽ tới được các vị trí tạo thành một hình vuông, giới hạn bởi ô góc trái dưới ~(x_i - t, y_i - t)~ và góc phải trên ~(x_i + t, y_i + t)~. Xét hình chữ nhật mà ~n~ hình vuông này giao nhau. Nếu hình chữ nhật này nằm trọn trong các vùng đất nguyền rủa thì ta không thể chọn ra vị trí ~(a, b)~ thoả mãn, ta phải tăng giới hạn ~t~ giây lên. Ngược lại ta có thể xét thời gian ~t~ nhỏ hơn.

Gọi hình chữ nhật mà ~n~ hình vuông giao nhau là ~S~.

Subtask ~1~:

Vì ~m = 1~ nên ta chỉ cần tìm phần giao của ~S~ với vùng đất nguyền rủa để kiểm tra.

Độ phức tạp: ~O(n \times \log(10^9))~.

Subtask ~2~:

Ta có thể bao hàm loại trừ để tính diện tích giao nhau giữa ~S~ và các vùng đất nguyền rủa. Gọi ~f(mask)~ là diện tích phần giao của ~S~ và các vùng đất thuộc ~mask~. Ta có:

~f(\{1, 2, ..., m\})~ = ~f(\{1\})~ + ~f(\{2\})~ + ... + ~f(\{m\})~ - ~f(\{1, 2\})~ - ~f(\{1, 3\})~ - ... - ~f(\{m - 1, m\})~ + ~f(\{1, 2, 3\})~ + ...

Độ phức tạp: ~O(\log(10^9) \times (n + 2^m))~.

Subtask ~3~:

Ta dùng kĩ thuật sweepline để kiểm tra ~S~ có hoàn toàn bị bao phủ hay không. Đầu tiên ta phải rời rạc hoá toạ độ. Vùng đất nguyền rủa thứ ~i~ sẽ ảnh hưởng các hàng ~[d_i, f_i]~ trong khoảng các cột ~[c_i, e_i]~. Ta có thể xét lần lượt các cột và cập nhật các hàng bị ảnh hưởng. Nếu một cột của ~S~ bị bao phủ tất cả các hàng thì không tồn tại ô ~(a, b)~ nào thoả mãn. Mỗi lần thêm đoạn hoặc xoá đoạn đi, ta phải cập nhật các hàng bị bao phủ. Vì ~m~ nhỏ nên ta chỉ cần duyệt trâu thay vì sử dụng CTDL.

ĐPT: ~O(\log(10^9) \times (n + m \times m))~.

Subtask ~4~:

Ta dùng CTDL Segtree để tối ưu subtask ~3~.

Độ phức tạp: ~O(\log(10^9) \times (n + m \times \log(n)))~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.