USACO 2024 - Tháng 1 - Hạng Vàng

Farmer John và \(Q\) (\(1 \leq Q \leq 2\cdot 10^5\)) con bò của ông đang đi nghỉ ở Manhattan, nhưng đàn bò đã trốn thoát và giờ tự do đi lại trong thành phố! Manhattan rất lớn — lớn đến mức \(N\) (\(1 \le N \le 2\cdot 10^5\)) con đường của nó kéo dài vô hạn trên mặt phẳng \(x\)-\(y\); thật tiện lợi, tất cả các đường đều hoàn toàn nằm ngang hoặc thẳng đứng. Mỗi đường ngang hoặc dọc có thể được mô hình hóa bởi phương trình dạng \(y=c_i\) hoặc \(x=c_i\), trong đó \(c_i\) là số nguyên từ \(0\) đến \(10^9\).

Farmer John biết chính xác mỗi con bò bắt đầu đi từ đâu và chúng đã trốn thoát bao lâu. Các con bò rất dễ đoán, nên mỗi con đi theo quy luật sau:

• Chúng chỉ đi về phía bắc (\(+y\)) hoặc phía đông (\(+x\)) với tốc độ một đơn vị mỗi giây.
• Nếu đang ở trên đúng một con đường, chúng tiếp tục đi theo hướng của con đường đó.
• Nếu đang ở giao điểm của hai con đường, chúng đi về phía bắc nếu đã đi được một số giây chẵn, và đi về phía đông nếu không.

Cho bố cục Manhattan và thông tin của từng con bò, hãy giúp Farmer John xác định vị trí hiện tại của chúng!

Dữ liệu vào

Dòng đầu chứa \(N\) và \(Q\).

\(N\) dòng tiếp theo mô tả các con đường. Mỗi đường được mô tả bởi một hướng (H hoặc V) và một tọa độ \(c_i\). Đảm bảo các con đường đôi một khác nhau.

\(Q\) dòng tiếp theo mô tả các con bò. Mỗi con được mô tả bởi ba số nguyên \((x_i,y_i,d_i)\), nghĩa là nó bắt đầu đi từ \((x_i,y_i)\) đúng \(d_i\) giây trước. Đảm bảo \((x_i,y_i)\) nằm trên một con đường nào đó và \(0 \le x_i,y_i,d_i \le 10^9\).

Dữ liệu ra

In \(Q\) dòng, trong đó dòng thứ \(i\) chứa vị trí hiện tại của con bò thứ \(i\).

Ví dụ

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Phân nhóm

• Các test 2-4 thỏa mãn \(N,Q,c_i,x_i,y_i,d_i \leq 100\).
• Các test 5-9 thỏa mãn \(N,Q\le 3000\).
• Các test 10-20 không có ràng buộc bổ sung.

Nguồn

USACO 2024 January Contest, Gold — Walking in Manhattan: https://usaco.org/index.php?page=viewproblem2&cpid=1377

Tác giả đề: Benjamin Qi

Farmer John đang tuyển thủ lĩnh mới cho đàn bò. Vì vậy, ông đã phỏng vấn \(N\) (\(2 \leq N \leq 10^9\)) con bò cho vị trí này. Sau mỗi cuộc phỏng vấn, ông gán cho ứng viên một điểm "cowmpetency" nguyên từ \(1\) đến \(C\) (\(1 \leq C \leq 10^4\)), tương quan với năng lực lãnh đạo của ứng viên.

Vì đã phỏng vấn quá nhiều bò, Farmer John quên hết điểm của chúng. Tuy nhiên, ông nhớ \(Q\) (\(1 \leq Q \leq \min(N-1,100)\)) cặp số \((a_i,h_i)\), trong đó bò \(h_i\) là con bò đầu tiên có điểm lớn hơn nghiêm ngặt điểm của tất cả các con bò từ \(1\) đến \(a_i\) (do đó \(1 \leq a_i < h_i \leq N\)).

Farmer John cho bạn \(Q\) cặp \((a_i,h_i)\). Hãy giúp ông đếm số dãy điểm cowmpetency phù hợp với những thông tin này! Đảm bảo có ít nhất một dãy như vậy. Vì số lượng có thể rất lớn, hãy in kết quả theo modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu chứa \(N\), \(Q\) và \(C\).

\(Q\) dòng tiếp theo, mỗi dòng chứa một cặp \((a_i,h_i)\). Đảm bảo mọi \(a_j\) đôi một khác nhau.

Dữ liệu ra

In số dãy điểm cowmpetency phù hợp với những gì Farmer John nhớ, theo modulo \(10^9+7\).

Ví dụ

6 2 3
2 3
4 5

6

1 1 2 1 3 1
1 1 2 1 3 2
1 1 2 1 3 3
1 1 2 2 3 1
1 1 2 2 3 2
1 1 2 2 3 3

10 1 20
1 3

399988086

Phân nhóm

• Các test 3-4 thỏa mãn \(N \leq 10\) và \(Q,C \leq 4\).
• Các test 5-7 thỏa mãn \(N,C \leq 100\).
• Các test 8-10 thỏa mãn \(N \leq 2000\) và \(C \leq 200\).
• Các test 11-15 thỏa mãn \(N,C \leq 2000\).
• Các test 16-20 không có ràng buộc bổ sung.

Nguồn

USACO 2024 January Contest, Gold — Cowmpetency: https://usaco.org/index.php?page=viewproblem2&cpid=1378

Tác giả đề: Suhas Nagar

Sau thời gian dài nghiên cứu, Bessie đã tìm ra được một thuật toán sắp xếp mới, được trình bày như sau: Tìm số nhỏ nhất trong những phần tử đã có, loại bỏ nó là thêm nó vào cuối của mảng.

Cô có \(N\) (\(1 \leq N \leq 2 \times 10^5\)) phần tử cần sắp xếp được kí hiệu là \(a_1, a_2, \ldots, a_N\) (\(1 \leq a_i \leq 10^{11}\)) và cô mất \(p\) giây để tìm ra phần tử nhỏ nhất trong \(p\) phần tử.

Nông dân John muốn giúp đỡ Bessie nên đã tuyển vài con bò để giúp Bessie hoàn thành công việc nhanh hơn, tuy nhiên chúng khá là lười biếng. Bessie thông minh đã nghĩ ra cách để tận dụng sự lười biếng của chúng: Cô chia những phần tử cần sắp xếp thành hai nửa, một nửa cô xử lý và phần còn lại giao cho những trợ lý của mình. Với mỗi phần tử mà Bessie xử lý, cô sử dụng thuật toán của mình như bình thường. Còn với những phần tử do các trợ lý đảm nhiệm, cô giao cho mỗi con bò trợ lý một phần tử quy định. Điều này có vẻ vô lý nhưng lại thuyết phục vì nông trại của nông dân John có rất nhiều bò nên có thể cho cô bao nhiêu trợ lý tùy thích. Mỗi con bò sau khi nhận được phần tử của mình sẽ được cho phép đi ngủ trong \(a_i\) giây, sau đó thêm nó vào cuối mảng sắp xếp khi chúng tỉnh giấc. Do Bessie là người chỉ đạo, khi cô và một con bò cùng thêm phần tử vào mảng một lúc, cô sẽ được ưu tiên đặt vào trước. Nếu nhiều hơn một trợ lý được đưa cho cùng một phần tử, chúng sẽ thêm vào mảng cùng một lúc.

Hãy giúp Bessie chia những phần tử để đảm bảo hoàn thành mảng sắp xếp trong thời gian ngắn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(T\) là số lượng các test case (\(1 \leq T \leq 10\)).
• Mỗi bài test case bao gồm:
  • Dòng đầu tiên chứa số lượng phần tử \(N\) trong mảng cần sắp xếp.
  • Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, …, a_N\) là những phần tử Bessie cần sắp xếp. Một số có thể xuất hiện nhiều lần.

Output

• Gồm \(T\) dòng, mỗi dòng gồm một số nguyên là thời gian ngắn nhất Bessie cần để sắp xếp lại mảng.

Scoring

• Subtask 1: \(N \leq 16\)
• Subtask 1: \(N \leq 150\)
• Subtask 1: \(\sum N≤5000\)
• Subtask 1: Không có ràng buộc gì thêm

Example

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

6
15
5
6