Xem mỗi quả bom là một đỉnh trong đồ thị, hai đỉnh ~(i, j)~ có cạnh nối nếu kích nổ quả bom ~i~ có thể khiến quả bom ~j~ nổ theo (và ngược lại). Khi đó, một miền liên thông sẽ chặn được đường đi từ điểm ~(0, 0)~ đến ~(n, n)~ nếu:

• ~\min(x_i) - l \le 0~ hoặc ~\max(y_i) + l \ge n~, và
• ~\max(x_i) + l \ge n~ hoặc ~\min(y_i) - l \le 0~.

Từ đây, ta có ý tưởng giải bài toán như sau:

Subtask 2

Ở subtask này, chúng ta có thể xét tất cả các cặp bom và kiểm tra điều kiện tạo cạnh nối, sau đó dựng đồ thị và kiểm tra các miền liên thông bằng cách sử dụng BFS/DFS hoặc DSU. Vì đồ thị của ta có thể có tối đa ~m^2~ cạnh, độ phức tạp của thuật toán này là ~O(m^2)~.

Subtask 3

Xét hai quả bom ~(x_i, y_i)~ và ~(x_j, y_j)~, chúng sẽ có cạnh nối nếu ~x_i - l \le x_j \le x_i + l~ và ~y_i - l \le y_j \le y_i + l~. Vì vậy, ta có thể sử dụng thuật toán đường quét như sau:

• Duyệt qua các quả bom theo chiều ~x~ tăng dần. Giả sử ta đang xét tới quả bom ~(x_i, y_i)~, ta sẽ sử dụng cấu trúc dữ liệu set để quản lý các quả bom có tọa độ ~x~ nằm trong khoảng ~[x_i - l, x_i]~.
• Ta sẽ nối cạnh từ quả bom ~(x_i, y_i)~ tới ~2~ quả bom bất kì: quả bom thứ nhất có tọa độ ~y~ nằm trong khoảng ~[y_i - l, y_i]~, và quả bom thứ hai có tọa độ ~y~ nằm trong khoảng ~[y_i, y_i + l]~ (vì sao chỉ cần nối ~2~ cạnh là đủ?)

Sau khi dựng được đồ thị, ta có thể làm tương tự subtask 2. Vì đồ thị của ta chỉ có tối đa ~2m~ cạnh, kết hợp với độ phức tạp của set, ta có được độ phức tạp cuối cùng là ~O(m \log m)~.