USACO 2022 - US Open - Hạng Bạch Kim

Bessie rất thích tải game về để giải trí sau những giờ học căng thẳng trên chiếc điện thoại của cô nàng dù cho chiếc màn hình bé nhỏ của điện thoại gây ra nhiều khó khăn cho cô nàng khi sử dụng (móng của nàng bò này rất to!!!!).

Cô nàng thường xuyên bị cuốn hút bởi tựa game hiện tại mà cô ta chơi. Tựa game đó có thể mô tả như sau: ban đầu sẽ có dãy gồm \(N\) \((1 \le N \le 262144)\) số nguyên dương \(a_1, a_2, \dots, a_N\) \((\forall i \in [1 \dots N], 1 \le a[i] \le 10^6)\), ở mỗi lượt chơi Bessie chọn \(2\) số liên tiếp cạnh nhau và thay thế chúng bằng một số nguyên lớn hơn hai số này (VD: cô nàng có thể thay cặp số cạnh nhau \((5, 7)\) bằng một số nguyên mới là \(8\)). Tựa game sẽ kết thúc sau \(N - 1\) lượt chơi, lúc này chỉ còn lại một số duy nhất trong dãy, mục tiêu của trò chơi là phải cực tiểu hoá số cuối cùng này.

Bessie biết rằng trò cái game này quá đỗi dễ dàng cho bạn, cho nên Bessie muốn bạn không chỉ chơi game tối ưu trên riêng dãy \(a\) mà còn phải chơi trên tất cả dãy con liên tiếp của dãy \(a\) nữa.

Hãy cho biết tổng tất cả các số bé nhất bạn có thể đạt được cho từng dãy trong \(\frac{N(N + 1)}{2}\) dãy con liên tiếp của \(a\) nhé.

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ \(2\) là các số \(a_1, a_2, \dots, a_N\).

Output

• Một dòng duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\): \(N \le 300\).
• Subtask \(2\): \(N \le 3000\).
• Subtask \(3\): Tất cả các giá trị của dãy không vượt quá \(40\).
• Subtask \(4\): Dãy được cho là dãy không giảm.
• Subtask \(5\): Không có thêm ràng buộc.

6
1 3 1 2 1 10

115

Cho một đồ thị có hướng \(N\) đỉnh, \(M\) cạnh \((2 \le N \le 10^5, 1 \le M \le 2 \times 10^5)\), mấy con bò của bác John già chơi một trò chơi \(2\) người như sau.

Đặt hai đồng xu lên \(2\) nút khác nhau của đồ thị. Ở mỗi lượt, người chơi thứ nhất - đầu não - sẽ chọn một đồng xu và đồng xu này sẽ đi theo một cạnh sang nút khác, người chơi thứ hai - móng guốc - sẽ chọn cạnh để di chuyển đồng xu mà người thứ nhất đã chọn. Một nước không thể có hai vua, một rừng không thể có hai hổ thì một nút không thể có hai đồng xu. Do đó, nếu như móng guốc không còn nước đi hợp lệ, thì đầu não sẽ là kẻ chiến thắng. Ngược lại, nếu trò chơi không thể kết thúc, móng guốc sẽ là kẻ chiến thắng. Biết rằng cả hai đều chơi tối ưu.

Có \(Q\) \((1 \le Q \le 10^5)\) ván đấu, mỗi ván được biểu diễn bằng hai nút thể hiện vị trí ban đầu của hai đồng xu. Với mỗi ván đấu, hãy cho biết ai sẽ là người chiến thắng!!!!

Input

• Dòng đầu tiên là \(2\) số \(N\) và \(M\).
• \(M\) dòng tiếp theo, mỗi dòng là \(2\) số nguyên \(a, b\) thể hiện có cạnh nối từ \(a\) đến \(b\).
• Đồ thị thoả mãn không có khuyên và không có cạnh nào xuất hiện nhiều hơn \(1\) lần.
• Dòng tiếp theo là số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng là hai số \(x\) và \(y\) \((1 \le x, y \le N, x \ne y)\).

Output

• \(Q\) dòng, mỗi dòng là một kí tự, trong đó B nếu như đầu não thắng và H nếu như móng guốc thắng.

Scoring

• Subtask \(1\): \(N \le 100, M \le 200\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Không có ràng buộc gì thêm.

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

BHHB

Nông dân John có \(N\) con bò \((2 \le N \le 3 \times 10^5)\) được đánh số từ \(1\) đến \(N\) như thường lệ. Những chú bò này đã xếp hàng thành một hoán vị \(p_1, p_2, \dots, p_N\). Bạn được cho một chuỗi dài \(N - 1\) chỉ bao gồm kí tự U và D. Hãy tìm ra số \(K \le N - 1\) lớn nhất sao cho tồn tại đãy con \(a_0, a_1, \dots, a_K\) của \(p\) thoả mãn với mọi \(1 \le j \le K, a_{j - 1} < a{j}\) nếu kí tự thứ \(j\) trong chuỗi là U và \(a_{j - 1} > a{j}\) nếu kí tự thứ \(j\) trong chuỗi là D.

Input

• Dòng đầu tiên là số \(N\).
• Dòng tiếp theo là các số \(p_1, p_2, \dots, p_N\).
• Dòng cuối cùng là chuỗi được cho.

Output

• Số \(K\) thoả mãn.

Scoring

• Subtask \(1\): \(N \le 500\).
• Subtask \(2\): \(N \le 5000\).
• Subtask \(3\): Phần đầu của chuỗi chỉ toàn kí tự U sau đó chỉ toàn kí tự D.
• Subtask \(4\): Không có thêm ràng buộc.

5
1 5 3 4 2
UDUD

4

5
1 5 3 4 2
UUDD

3