APIO 2018

Phố Wu-Fu là một phố cực kỳ thẳng có thể được mô tả như là một dải số một chiều, và mỗi vị trí của tòa nhà trên đường phố có thể được biểu diễn bằng một số. Nhà du hành xuyên thời gian Xiao-Ming biết rằng có \(n\) cửa hàng thuộc \(k\) loại cửa hàng đã từng mở cửa, đã mở cửa, hoặc sẽ mở cửa trên phố. Cửa hàng thứ \(i\) có thể được mô tả bằng bốn số nguyên: \(x_i, t_i, a_i, b_i\), tương ứng là vị trí của cửa hàng, loại cửa hàng, năm bắt đầu kinh doanh và năm cửa hàng đóng cửa.

Nhà du hành xuyên thời gian Xiao-Ming muốn chọn một năm nhất định và một vị trí nhất định trên Phố Wu-Fu để sinh sống. Ông đã thu hẹp danh sách sở thích của mình xuống \(q\) cặp vị trí/năm. Cặp thứ \(i\) có thể được mô tả bằng hai số nguyên: \(l_i, y_i\), biểu diễn vị trí và năm của cặp đó. Bây giờ ông ta muốn đánh giá chất lượng cuộc sống của các cặp này. Ông xác định chỉ số bất tiện của cặp vị trí/năm là mức độ khó tiếp cận của loại cửa hàng có mức độ khó tiếp cận lớn nhất của cặp đó. Mức độ khó tiếp cập của một cặp vị trí/năm đối với loại cửa hàng \(t\) được định nghĩa là khoảng cách từ vị trí đó đến cửa hàng loại \(t\) gần nhất mà được mở trong năm đó. Chúng ta nói rằng cửa hàng thứ \(i\) được mở trong năm \(y\) nếu \(a_i \le y \le b_i\). Lưu ý rằng trong một vài năm, phố Wu-Fu có thể không có tất cả \(k\) loại cửa hàng trên phố. Trong trường hợp đó, chỉ số bất tiện được định nghĩa là \(-1\).

Nhiệm vụ của bạn là giúp Xiao-Ming tìm ra chỉ số bất tiện của từng cặp vị trí/năm.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(n\), \(k\) và \(q\): số lượng cửa hàng, số loại và số truy vấn (\(1 \le n, q \le 3 \cdot 10^5\), \(1 \le k \le n\)).

\(n\) dòng tiếp theo chứa các mô tả của các cửa hàng. Mỗi mô tả bao gồm bốn số nguyên: \(x_i\), \(t_i\), \(a_i\) và \(b_i\) (\(1 \le x_i, a_i, b_i \le 10^8\), \(1 \le t_i \le k\), \(a_i \le b_i\)).

\(q\) dòng tiếp theo chứa các truy vấn. Mỗi truy vấn bao gồm hai số nguyên: \(l_i\) và \(y_i\) (\(1 \le l_i, y_i \le 10^8\)).

Dữ liệu ra

Ghi \(q\) số nguyên: với mỗi truy vấn ghi ra chỉ số bất tiện của nó.

Phân nhóm

Ví dụ

4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10

4
2
-1
-1

2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

0
0
-1

1 1 1
100000000 1 1 1
1 1

99999999

Giải thích

Trong ví dụ đầu tiên có bốn cửa hàng, hai loại và bốn truy vấn.

• Truy vấn đầu tiên: Xiao-Ming sống ở vị trí 5 trong năm 3. Trong năm này, các cửa hàng 1 và 2 đang mở, khoảng cách đến cửa hàng 1 là 2, khoảng cách đến cửa hàng 2 là 4. Vậy tối đa là 4.

• Truy vấn thứ hai: Xiao-Ming sống ở vị trí 5 trong năm 6. Trong năm này, các cửa hàng 1 và 3 đang mở, khoảng cách đến cửa hàng 1 là 2, khoảng cách đến cửa hàng 3 là 2. Vậy tối đa là 2.

• Truy vấn thứ ba: Xiao-Ming sống ở vị trí 5 trong năm 9. Trong năm này, các cửa hàng 1 và 4 đang mở, cả hai đều có loại 1, vì vậy không có cửa hàng loại 2, chỉ số bất tiện là \(-1\).

• Tình huống tương tự trong truy vấn thứ tư.

Trong ví dụ thứ hai có hai cửa hàng, một loại và ba truy vấn. Cả hai cửa hàng đều có vị trí 1 và trong tất cả các truy vấn, Xiao-Ming sống ở vị trí 1. Trong hai truy vấn đầu tiên, ít nhất một cửa hàng đang mở, vì vậy câu trả lời là 0, ở truy vấn thứ ba cả hai cửa hàng đều đóng cửa, vì vậy câu trả lời là \(-1\).

Trong ví dụ thứ ba có một cửa hàng và một truy vấn. Khoảng cách giữa các địa điểm là 99999999.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2018, được lưu trong kho đề APIO.

Cho \(n\) hình tròn \(c_1, c_2, \ldots, c_n\) trên mặt phẳng Đề-các. Hãy thực hiện những việc sau:

1. Lựa chọn hình tròn \(c_i\) có bán kính lớn nhất. Nếu có nhiều lựa chọn cùng có bán kính (lớn nhất), chọn hình có chỉ số nhỏ nhất (nghĩa là \(i\) nhỏ nhất).

2. Xóa hình tròn \(c_i\) và tất cả các hình tròn giao với \(c_i\). Hai hình tròn giao nhau nếu tồn tại một điểm thuộc cả hai hình tròn. Một điểm thuộc một hình tròn nếu nó nằm trong hình tròn hoặc nó nằm trên biên của hình tròn đó.

3. Lặp lại công việc 1 và 2 cho đến khi không còn hình tròn nào.

{{asset:apio18circle/circles.png}}

Ta nói \(c_i\) bị loại bỏ bởi \(c_j\) nếu \(c_j\) là hình tròn được chọn trong lần lặp mà \(c_i\) bị xóa. Đối với mỗi hình tròn, tìm ra hình tròn loại bỏ nó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\), là số lượng hình tròn (\(1 \le n \le 3 \cdot 10^5\)).

Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên \(x_i, y_i, r_i\), là toạ độ theo trục x, tọa độ theo trục y và bán kính của hình tròn \(c_i\) (\(-10^9 \le x_i, y_i \le 10^9\), \(1 \le r_i \le 10^9\)).

Dữ liệu ra

Ghi ra \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) trên dòng đầu tiên, trong đó \(a_i\) có nghĩa là \(c_i\) bị loại bỏ bởi \(c_{a_i}\).

Phân nhóm

Ví dụ

11
9 9 2
13 2 1
11 8 2
3 3 2
3 12 1
12 14 1
9 8 5
2 8 2
5 2 1
14 4 2
14 14 1

7 2 7 4 5 6 7 7 4 7 6

Giải thích

Hình ảnh trong phát biểu minh họa cho ví dụ đầu tiên.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2018, được lưu trong kho đề APIO.

Mạng lưới đường phố của Byteburg bao gồm \(n\) giao lộ được liên kết bởi \(m\) đoạn đường hai chiều. Gần đây, Byteburg đã được chọn để tổ chức giải vô địch Duathlon sắp tới. Cuộc thi này bao gồm hai chặng: chặng chạy bộ, tiếp theo là chặng đi xe đạp.

Tuyến đường cho cuộc thi phải được xây dựng theo cách thức sau. Đầu tiên, ba giao lộ phân biệt nhau \(s\), \(c\) và \(f\) được chọn làm điểm xuất phát, chuyển đổi và kết thúc. Sau đó, tuyến đường cho cuộc thi sẽ được xây dựng. Tuyến đường sẽ bắt đầu ở \(s\), đi qua \(c\) và kết thúc ở \(f\). Vì lý do an toàn, tuyến đường chỉ qua mỗi giao lộ nhiều nhất một lần.

Trước khi xây dựng tuyến đường, thị trưởng muốn tính toán số cách để chọn giao lộ \(s\), \(c\) và \(f\) để có thể xây dựng tuyến đường thỏa mãn. Hãy giúp ông ta tính ra số này.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(n\) và \(m\): là số giao lộ và số đoạn đường. Tiếp theo là \(m\) dòng chứa mô tả các đoạn đường (\(1 \le n \le 10^5\), \(1 \le m \le 2 \cdot 10^5\)). Mỗi đoạn đường được mô tả bằng cặp hai số nguyên \(v_i\), \(u_i\), chỉ hai giao lộ có đoạn đường liên kết (\(1 \le v_i, u_i \le n\), \(v_i \ne u_i\)). Giữa mỗi cặp giao lộ, có tối đa một đường nối chúng.

Dữ liệu ra

Ghi ra số cách để chọn các giao lộ \(s\), \(c\) và \(f\) làm điểm xuất phát, chuyển đổi và kết thúc, để có thể xây dựng tuyến đường thỏa mãn cho cuộc thi.

Phân nhóm

Ví dụ

4 3
1 2
2 3
3 4

8

4 4
1 2
2 3
3 4
4 2

14

Giải thích

Trong ví dụ thứ nhất có 8 cách để chọn bộ ba \((s, c, f)\): \((1, 2, 3)\), \((1, 2, 4)\), \((1, 3, 4)\), \((2, 3, 4)\), \((3, 2, 1)\), \((4, 2, 1)\), \((4, 3, 1)\), \((4, 3, 2)\).

Trong ví dụ thứ hai có 14 cách để chọn bộ ba \((s, c, f)\): \((1, 2, 3)\), \((1, 2, 4)\), \((1, 3, 4)\), \((1, 4, 3)\), \((2, 3, 4)\), \((2, 4, 3)\), \((3, 2, 1)\), \((3, 2, 4)\), \((3, 4, 1)\), \((3, 4, 2)\), \((4, 2, 1)\), \((4, 2, 3)\), \((4, 3, 1)\), \((4, 3, 2)\).

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2018, được lưu trong kho đề APIO.