JOI 2015 Final Camp - Ngày 2

Có \(N\) tòa nhà dọc đại lộ, đánh số từ sân bay đến nơi lưu trú; mọi chiều cao đôi một khác nhau. Chỉ có thể trang trí một dãy tòa nhà có chiều cao tăng nghiêm ngặt theo hướng từ sân bay.

Với mỗi \(i\), đặt \(A_i\) là số tòa nhà lớn nhất có thể chọn khi bắt buộc chọn tòa \(i\) và tòa \(i\) phải là tòa được chọn gần nơi lưu trú nhất. K đã nhận một dãy \(B_1,\ldots,B_{N-1}\) và cho rằng JOI đã bỏ quên đúng một phần tử của dãy \(A\). Hãy đếm số dãy giá trị khác nhau \(A_1,\ldots,A_N\) có thể sinh ra từ một cách gán các chiều cao đôi một khác nhau và trở thành \(B\) sau khi xóa một phần tử.

Dữ liệu vào

Dòng đầu chứa \(N\). Mỗi trong \(N-1\) dòng sau chứa \(B_j\).

Dữ liệu ra

In số dãy \(A\) thỏa mãn.

Ràng buộc

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le8\).
• Nhóm 2 (30 điểm): \(N\le300\).
• Nhóm 3 (60 điểm): không có ràng buộc bổ sung.

Ví dụ

4
1
1
2

5

8
1
1
2
1
2
3
1

15

JOI có \(N\) nhân viên, tất cả làm việc trong khoảng thời gian từ 0 đến \(M\) và đều ở trong công ty tại hai thời điểm đó. Hôm nay, nhân viên \(i\) ra ngoài đúng một lần tại \(S_i\) và trở lại tại \(T_i\). Không có hai sự kiện ra hoặc vào nào cùng thời điểm.

Cửa có khóa, ban đầu khóa đóng. Từ bên trong, ai cũng có thể mở hoặc đóng khóa; từ bên ngoài, chỉ người có chìa mới làm được. Khi trở lại, mỗi người phải vào được: họ phải có chìa hoặc khóa đang mở. Khi trở lại, hoặc khi người có chìa rời công ty, họ tùy ý đóng khóa; người không có chìa không thể đóng khóa khi rời đi. Nhân viên chỉ được thao tác khóa đúng lúc chính mình ra hoặc vào, và chìa không được chuyển giữa người.

Giám đốc phát chìa cho đúng \(K\) người. Hãy tối đa hóa tổng thời gian khóa ở trạng thái đóng trong \([0,M]\).

Dữ liệu vào

Dòng đầu chứa \(N,M,K\). Mỗi trong \(N\) dòng sau chứa \(S_i,T_i\).

Dữ liệu ra

In tổng thời gian đóng khóa lớn nhất.

Ràng buộc

Toàn bộ \(2N\) giá trị \(S_i,T_i\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le20\), \(M\le1\,000\,000\).
• Nhóm 2 (90 điểm): không có ràng buộc bổ sung.

Ví dụ

4 20 2
3 11
5 15
6 10
12 18

13

20 100000 8
29930 89724
56133 70462
28063 78568
32483 64351
9410 20176
55809 62944
32450 85190
73536 73966
20452 78868
45458 63484
8286 47425
76018 81622
16736 49308
85383 94641
25100 40002
22158 22821
23508 41781
61709 98882
58110 78431
28448 89247

72454

IOI có \(N\) thành phố, ban đầu chưa có đường. Trong năm \(i\) có kế hoạch cải thiện giao thông giữa \(A_i\) và \(B_i\); \(T_i=1\) nghĩa là kế hoạch được thực hiện trong năm ấy, còn \(T_i=2\) nghĩa là bị hủy.

Khi một kế hoạch được thực hiện:

• Nếu hai thành phố chưa liên thông bởi các đường đã xây, xây một đường hai chiều chưa trải nhựa nối trực tiếp chúng.
• Nếu đã liên thông, xét mọi đường đi dùng ít cạnh nhất giữa chúng và trải nhựa mọi cạnh chưa trải thuộc ít nhất một đường đi ngắn nhất như vậy. Đường đã trải không được trải lại.

Với từng kế hoạch bị hủy, hãy xét trạng thái lịch sử tại đúng thời điểm ấy và giả sử chỉ riêng kế hoạch đó được thực hiện thêm. In số đường sẽ được trải nhựa; nếu nó sẽ xây đường mới thì in -1. Giả định này không làm thay đổi trạng thái cho những năm sau.

Dữ liệu vào

Dòng đầu chứa \(N,Q\). Mỗi trong \(Q\) dòng sau chứa \(T_i,A_i,B_i\).

Dữ liệu ra

Với mỗi kế hoạch có \(T_i=2\), theo thứ tự thời gian, in đáp án trên một dòng.

Ràng buộc

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le1000\), \(Q\le3000\).
• Nhóm 2 (25 điểm): tồn tại \(1\le P\le Q-1\) sao cho \(T_i=1\) với \(i\le P\) và \(T_i=2\) với \(i>P\).
• Nhóm 3 (25 điểm): với mọi kế hoạch được thực hiện, ngay trước khi thực hiện, hai đầu hoặc chưa liên thông, hoặc có một đường đi giữa chúng dùng không quá 200 đường.
• Nhóm 4 (25 điểm): có không quá 200 chỉ số \(i\) với \(T_i=2\).
• Nhóm 5 (15 điểm): không có ràng buộc bổ sung.

Ví dụ

3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3

1
-1
0
1

6 8
1 1 3
1 6 1
1 2 5
2 3 6
1 3 6
1 4 1
2 4 3
2 2 5

2
1
1

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

0
1
0
-1