| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2022 - Tickets | 100 (p) | 4.0s | 512M |
| 2 | USACO 2022 - Paired Up | 100 (p) | 4.0s | 512M |
| 3 | USACO 2022 - HILO | 100 (p) | 4.0s | 512M |
Bessie đang tham gia một chuyến đi bộ đường dài! Tuyến đường mà cô đang đi qua gồm \(N\) trạm kiểm soát được đánh số \(1\ldots N\) (\(1 \le N \le 10^5\)).
Có \(K\) vé (\(1 \le K \le 10^5\)) được bán. Vé thứ \(i\) có thể được mua tại trạm kiểm soát \(c_i\) (\(1 \le c_i \le N\)) với giá \(p_i\) (\(1 \le p_i \le 10^9\)), và cho phép đi vào tất cả các trạm kiểm soát trong đoạn \([a_i,b_i]\) (\(1 \le a_i \le b_i \le N\)). Trước khi đi vào bất kỳ trạm kiểm soát nào, Bessie phải mua một vé cho phép cô đi vào trạm đó. Sau khi có quyền đi vào một trạm kiểm soát, Bessie có thể quay lại trạm ấy vào bất kỳ thời điểm nào trong tương lai. Cô có thể di chuyển giữa hai trạm kiểm soát mà mình có quyền đi vào, bất kể số hiệu của chúng có chênh nhau \(1\) hay không.
Với mỗi \(i \in [1,N]\), giả sử ban đầu Bessie chỉ có quyền đi vào trạm kiểm soát \(i\). Hãy cho biết tổng chi phí nhỏ nhất để mua quyền đi vào cả trạm kiểm soát \(1\) và trạm kiểm soát \(N\). Nếu không thể làm được, hãy in ra \(-1\).
Dòng đầu tiên chứa \(N\) và \(K\).
Mỗi dòng trong \(K\) dòng tiếp theo chứa bốn số nguyên \(c_i\), \(p_i\), \(a_i\) và \(b_i\), tương ứng với vé thứ \(i\) (\(1 \le i \le K\)).
In ra \(N\) dòng, mỗi dòng ứng với một trạm kiểm soát.
Ví dụ 1
7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6-1
-1
-1
1111
10100
110100
-1Nếu Bessie bắt đầu tại trạm kiểm soát \(i=4\), một cách để cô mua quyền đi vào các trạm kiểm soát \(1\) và \(N\) là:
USACO 2021 December Contest, Platinum — Tickets. Tác giả: Benjamin Qi.
Có tổng cộng \(N\) con bò (\(1 \le N \le 5000\)) trên trục số, mỗi con thuộc giống Holstein hoặc Guernsey. Giống của con bò thứ \(i\) được cho bởi \(b_i \in \{H,G\}\), vị trí của nó được cho bởi \(x_i\) (\(0 \le x_i \le 10^9\)), và khối lượng của nó được cho bởi \(y_i\) (\(1 \le y_i \le 10^5\)).
Theo hiệu lệnh của Farmer John, một số con bò sẽ ghép thành các cặp sao cho:
Bạn cần xác định phạm vi các giá trị có thể có của tổng khối lượng những con bò không được ghép cặp. Cụ thể:
Dòng đầu tiên chứa \(T\), \(N\) và \(K\).
Với mỗi \(1 \le i \le N\), dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa \(b_i,x_i,y_i\), tương ứng với con bò thứ \(i\). Dữ liệu bảo đảm \(0 \le x_1 < x_2 < \cdots < x_N \le 10^9\).
In ra tổng khối lượng nhỏ nhất hoặc lớn nhất có thể của những con bò không được ghép cặp, tùy theo giá trị của \(T\).
Lưu ý: Giới hạn bộ nhớ của bài này là 512 MB, gấp đôi giới hạn mặc định.
Ví dụ 1
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 916Hai con bò \(2\) và \(3\) có thể ghép cặp vì khoảng cách giữa chúng là \(1\), không vượt quá \(K=4\). Cách ghép này là cực đại vì con bò \(1\), con Guernsey duy nhất còn lại, cách con bò \(4\) một khoảng \(5\) và cách con bò \(5\) một khoảng \(7\), đều lớn hơn \(K=4\). Tổng khối lượng của những con bò không được ghép cặp là \(1+6+9=16\).
Ví dụ 2
1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 96Hai con bò \(1\) và \(2\) có thể ghép cặp vì khoảng cách giữa chúng là \(2 \le K=4\), và hai con bò \(3\) và \(5\) có thể ghép cặp vì khoảng cách giữa chúng là \(4 \le K=4\). Cách ghép này là cực đại vì chỉ còn lại con bò \(4\). Tổng khối lượng của những con bò không được ghép cặp chính là khối lượng của con bò duy nhất còn lại, bằng \(6\).
Ví dụ 3
2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 5401893Đáp án của ví dụ này là \(18+465+870+540=1893\).
USACO 2021 December Contest, Platinum — Paired Up. Tác giả: Benjamin Qi.
Bessie biết một số \(x+0.5\), trong đó \(x\) là một số nguyên từ \(0\) đến \(N\), kể cả hai đầu mút (\(1 \le N \le 5000\)).
Elsie đang cố đoán số này. Cô có thể đặt câu hỏi "số \(i\) cao hay thấp?" với một số nguyên \(i\) từ \(1\) đến \(N\), kể cả hai đầu mút. Bessie trả lời "HI!" nếu \(i\) lớn hơn \(x+0.5\), hoặc "LO!" nếu \(i\) nhỏ hơn \(x+0.5\).
Elsie nghĩ ra chiến lược sau để đoán số của Bessie. Trước khi đưa ra bất kỳ dự đoán nào, cô lập một danh sách gồm \(N\) số, trong đó mỗi số từ \(1\) đến \(N\) xuất hiện đúng một lần (nói cách khác, danh sách là một hoán vị có kích thước \(N\)). Sau đó, cô lần lượt duyệt danh sách và đoán các số theo thứ tự xuất hiện. Tuy nhiên, Elsie bỏ qua mọi dự đoán không cần thiết. Cụ thể, nếu Elsie sắp đoán số \(i\) và trước đó đã đoán một số \(j<i\) mà Bessie trả lời "HI!", Elsie sẽ không đoán \(i\) và chuyển sang số tiếp theo trong danh sách. Tương tự, nếu Elsie sắp đoán số \(i\) và trước đó đã đoán một số \(j>i\) mà Bessie trả lời "LO!", Elsie sẽ không đoán \(i\) và chuyển sang số tiếp theo trong danh sách. Có thể chứng minh rằng với chiến lược này, Elsie luôn xác định duy nhất được \(x\), bất kể cô lập hoán vị nào.
Nếu nối tất cả câu trả lời "HI" hoặc "LO" của Bessie thành một xâu duy nhất \(S\), số lần Bessie nói "HILO" được định nghĩa là số xâu con độ dài \(4\) của \(S\) bằng "HILO".
Bessie biết Elsie sẽ sử dụng chiến lược này và đã chọn giá trị của \(x\), nhưng cô không biết Elsie sẽ dùng hoán vị nào. Hãy tính tổng số lần Bessie nói "HILO" trên tất cả các hoán vị mà Elsie có thể chọn, lấy modulo \(10^9+7\).
Dòng duy nhất chứa \(N\) và \(x\).
In ra tổng số lần xuất hiện của "HILO", lấy modulo \(10^9+7\).
Ví dụ 1
4 217Trong test này, số của Bessie là \(2.5\).
Chẳng hạn, nếu hoán vị của Elsie là \((4,1,3,2)\) thì Bessie sẽ nói "HILOHILO", chứa tổng cộng hai lần "HILO". Một ví dụ khác, nếu hoán vị của Elsie là \((3,1,2,4)\) thì Bessie sẽ nói "HILOLO", chứa tổng cộng một lần "HILO".
Ví dụ 2
60 10508859913Hãy bảo đảm in tổng sau khi lấy modulo \(10^9+7\).
USACO 2021 December Contest, Platinum — HILO. Tác giả: Richard Qi.