JOI 2024 - Tuyển chọn mùa xuân - Ngày 3

JOI-kun rất thích sưu tập thẻ trong một trò chơi. Mỗi thẻ có hai số nguyên biểu thị sức mạnh và chi phí. Để có thẻ mới, JOI-kun mang \(N\) thẻ đến nơi đổi thẻ. Các thẻ được đánh số từ \(1\) đến \(N\); thẻ \(i\) có sức mạnh \(S_i\) và chi phí \(V_i\).

Tại đây có hai loại máy. Khi đưa hai thẻ \(A\) và \(B\) vào một máy, JOI-kun nhận được một thẻ \(C\) theo quy tắc sau:

• Máy thứ nhất tạo thẻ có sức mạnh bằng giá trị lớn hơn trong hai sức mạnh của \(A,B\), và chi phí bằng giá trị lớn hơn trong hai chi phí của \(A,B\).
• Máy thứ hai tạo thẻ có sức mạnh bằng giá trị nhỏ hơn trong hai sức mạnh của \(A,B\), và chi phí bằng giá trị nhỏ hơn trong hai chi phí của \(A,B\).

JOI-kun muốn đổi thẻ đúng \(N-1\) lần để cuối cùng chỉ còn một thẻ. Ban đầu, cậu xếp các thẻ thành một hàng theo thứ tự từ thẻ \(1\) đến thẻ \(N\), rồi lặp lại thao tác sau đúng \(N-1\) lần:

Chọn hai thẻ kề nhau, lấy chúng ra khỏi hàng và đổi bằng một trong hai máy. Đặt thẻ mới vào vị trí của hai thẻ vừa lấy ra.

Sức mạnh và chi phí của thẻ cuối cùng phụ thuộc vào các thao tác được chọn. JOI-kun có danh sách \(M\) thẻ muốn nhận được. Thẻ thứ \(j\) trong danh sách được biểu diễn bởi cặp \((T_j,W_j)\), tương ứng với sức mạnh và chi phí.

Cho thông tin về các thẻ ban đầu và danh sách mong muốn, hãy xác định tất cả các thẻ trong danh sách mà JOI-kun có thể nhận được sau đúng \(N-1\) thao tác.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,M\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i,V_i\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(T_j,W_j\).

Dữ liệu ra

In trên một dòng chỉ số của tất cả các thẻ trong danh sách có thể nhận được sau đúng \(N-1\) thao tác, theo thứ tự tăng dần và cách nhau bởi dấu cách. Nếu không có thẻ nào như vậy, in một dòng trống.

Ràng buộc

• \(2 \le N \le 200000\).
• \(1 \le M \le 200000\).
• \(1 \le S_i \le 10^9\) và \(1 \le V_i \le 10^9\) với mọi \(1 \le i \le N\).
• \(1 \le T_j \le 10^9\) và \(1 \le W_j \le 10^9\) với mọi \(1 \le j \le M\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(11\) điểm: \(N \le 20\), \(M \le 10\).
2. \(38\) điểm: \(N \le 2000\), \(M \le 10\).
3. \(22\) điểm: \(M \le 10\).
4. \(29\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 3
1 3
2 2
4 4
1 3
1 1
2 3
2 1
4 4

1 3

2 2
1 1
2 2
1 2
2 1

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

3 4 5 8

Giới hạn

Giới hạn thời gian là \(4\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

Đất nước IOI có \(N\) thị trấn, được đánh số từ \(0\) đến \(N-1\), và \(N-1\) con đường, được đánh số từ \(0\) đến \(N-2\). Đường \(j\) nối hai chiều thị trấn \(U_j\) và thị trấn \(V_j\). Có thể đi giữa hai thị trấn bất kỳ bằng cách đi qua một số con đường.

Mỗi thị trấn có một nhà hàng. Loại nhà hàng ở thị trấn \(i\) được biểu diễn bởi số nguyên \(F_i\):

• \(F_i=0\): nhà hàng nước ép.
• \(F_i=1\): nhà hàng trứng ốp lết.
• \(F_i=2\): nhà hàng kem.

Rie là hướng dẫn viên du lịch và đang xây dựng chuyến tham quan mang tên JOI Tour, gồm các bước sau:

1. Chọn một thị trấn \(i_0\) có nhà hàng nước ép và bắt đầu chuyến đi tại đó.
2. Ghé nhà hàng nước ép ở thị trấn \(i_0\).
3. Chọn một thị trấn \(i_1\) có nhà hàng trứng ốp lết, rồi đi xe buýt từ \(i_0\) đến \(i_1\) theo đường đi ngắn nhất.
4. Ghé nhà hàng trứng ốp lết ở thị trấn \(i_1\).
5. Chọn một thị trấn \(i_2\) có nhà hàng kem, rồi đi xe buýt từ \(i_1\) đến \(i_2\) theo đường đi ngắn nhất.
6. Ghé nhà hàng kem ở thị trấn \(i_2\).
7. Kết thúc chuyến đi tại thị trấn \(i_2\).

Để khách không cảm thấy nhàm chán, Rie chỉ chọn ba thị trấn sao cho không có con đường nào được đi qua hai lần trong chuyến đi. Một JOI Tour như vậy được gọi là tốt.

Bạn cần tính số bộ ba \((i_0,i_1,i_2)\) thỏa mãn đồng thời các điều kiện:

• Nhà hàng ở \(i_0\) là nhà hàng nước ép.
• Nhà hàng ở \(i_1\) là nhà hàng trứng ốp lết.
• Nhà hàng ở \(i_2\) là nhà hàng kem.
• Khi đi từ \(i_0\) đến \(i_1\), rồi từ \(i_1\) đến \(i_2\), đều theo đường đi ngắn nhất, không con đường nào được đi qua hai lần.

Sẽ có \(Q\) lần thay đổi loại nhà hàng. Trong lần thay đổi thứ \(k+1\) (\(0 \le k \le Q-1\)), bạn được cung cấp hai số nguyên \(X_k,Y_k\). Nhà hàng ở thị trấn \(X_k\) được đổi sang loại \(Y_k\): nước ép nếu \(Y_k=0\), trứng ốp lết nếu \(Y_k=1\), kem nếu \(Y_k=2\). Ngay sau mỗi lần thay đổi, bạn phải cập nhật số JOI Tour tốt và trả kết quả cho Rie.

Chi tiết cài đặt

Bạn cần nộp một tệp tên joitour.cpp. Tệp này phải dùng chỉ thị #include để nạp joitour.h và cài đặt các hàm sau:

void init(int N, std::vector<int> F, std::vector<int> U,
          std::vector<int> V, int Q);
void change(int X, int Y);
long long num_tours();

Hàm init được gọi đúng một lần ở đầu chương trình để cung cấp thông tin ban đầu. Tham số N là số thị trấn, F là mảng có độ dài \(N\) với F[i] là loại nhà hàng ở thị trấn \(i\). Hai mảng U,V có độ dài \(N-1\); U[j],V[j] là hai đầu của đường \(j\). Tham số Q là số lần thay đổi loại nhà hàng.

Hàm change được gọi đúng \(Q\) lần. Trong lần gọi thứ \(k+1\), X là thị trấn \(X_k\) và Y là loại nhà hàng mới \(Y_k\). Loại mới được bảo đảm khác loại hiện tại.

Hàm num_tours được gọi ngay sau init và ngay sau mỗi lần gọi change, tổng cộng \(Q+1\) lần. Mỗi lần gọi phải trả về số JOI Tour tốt ở thời điểm đó.

Bạn được phép cài đặt thêm hàm phụ và khai báo biến toàn cục. Chương trình của bạn không được đọc hoặc ghi qua đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Chương trình chấm mẫu

Gói tệp được cung cấp chứa chương trình chấm mẫu grader.cpp, tệp khai báo joitour.h, tệp cài đặt mẫu joitour.cpp và compile.sh. Để kiểm tra chương trình, đặt grader.cpp, joitour.cpp và joitour.h trong cùng thư mục và dùng lệnh:

g++ -std=gnu++20 -O2 -o grader grader.cpp joitour.cpp

Cũng có thể chạy compile.sh. Khi biên dịch thành công, tệp thực thi grader được tạo ra. Chương trình chấm thật khác chương trình chấm mẫu. Chương trình chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và in kết quả ra đầu ra chuẩn.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(F_0,F_1,\ldots,F_{N-1}\).
• Trong \(N-1\) dòng tiếp theo, dòng thứ \(j+1\) chứa hai số nguyên \(U_j,V_j\) (\(0 \le j \le N-2\)).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k+1\) chứa hai số nguyên \(X_k,Y_k\) (\(0 \le k \le Q-1\)).

Dữ liệu ra

Sau mỗi lần gọi num_tours, chương trình chấm mẫu in giá trị trả về trên một dòng. Vì vậy, có \(Q+1\) dòng kết quả.

Ràng buộc

• \(3 \le N \le 200000\).
• \(0 \le F_i \le 2\) với mọi \(0 \le i \le N-1\).
• \(0 \le U_j<V_j \le N-1\) với mọi \(0 \le j \le N-2\).
• Có thể đi giữa hai thị trấn bất kỳ bằng cách đi qua các con đường.
• \(0 \le Q \le 50000\).
• \(0 \le X_k \le N-1\) và \(0 \le Y_k \le 2\) với mọi \(0 \le k \le Q-1\).
• Trong mỗi lần gọi change, loại nhà hàng mới khác loại nhà hàng hiện tại.
• Tất cả các giá trị được cung cấp đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(N \le 400\), \(Q \le 100\).
2. \(8\) điểm: \(N \le 4000\), \(Q \le 1000\).
3. \(6\) điểm: \(Q=0\).
4. \(16\) điểm: \(U_j=j\), \(V_j=j+1\) với mọi \(0 \le j \le N-2\).
5. \(16\) điểm: \(U_j=\lfloor j/2\rfloor\), \(V_j=j+1\) với mọi \(0 \le j \le N-2\).
6. \(34\) điểm: \(N \le 100000\), \(Q \le 25000\).
7. \(14\) điểm: Không có ràng buộc bổ sung.

Ký hiệu \(\lfloor j/2\rfloor\) là số nguyên lớn nhất không vượt quá \(j/2\).

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

3
0 1 2
0 1
1 2
0

Dữ liệu ra của trình chấm mẫu:

1

Giải thích

Các lời gọi tương ứng là:

Chỉ có một JOI Tour tốt, ứng với \((i_0,i_1,i_2)=(0,1,2)\). Thị trấn \(0\) có nhà hàng nước ép vì \(F_0=0\); thị trấn \(1\) có nhà hàng trứng ốp lết vì \(F_1=1\); thị trấn \(2\) có nhà hàng kem vì \(F_2=2\). Đi từ \(0\) đến \(1\), rồi từ \(1\) đến \(2\) theo đường đi ngắn nhất không đi qua đường nào hai lần. Vì vậy, lần gọi num_tours đầu tiên trả về \(1\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4,6,7\).

Ví dụ 2

Dữ liệu vào của trình chấm mẫu:

3
0 1 2
0 1
1 2
2
2 0
0 2

Dữ liệu ra của trình chấm mẫu:

1
0
1

Giải thích

Các lời gọi tương ứng là:

Ban đầu chỉ có JOI Tour tốt \((0,1,2)\), nên giá trị trả về đầu tiên là \(1\).

Sau lần thay đổi thứ nhất, nhà hàng kem ở thị trấn \(2\) trở thành nhà hàng nước ép. Không còn nhà hàng kem nào, nên không có JOI Tour tốt và giá trị trả về thứ hai là \(0\).

Sau lần thay đổi thứ hai, nhà hàng nước ép ở thị trấn \(0\) trở thành nhà hàng kem. Khi đó có đúng một JOI Tour tốt \((2,1,0)\), nên giá trị trả về thứ ba là \(1\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4,6,7\).

Ví dụ 3

Dữ liệu vào của trình chấm mẫu:

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

Dữ liệu ra của trình chấm mẫu:

3
0
4
4
0
4
5
5

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,5,6,7\).

Giới hạn

Giới hạn thời gian là \(3\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

Tháp IOI rất cao và có một cầu thang gồm \(10^{100}\) bậc, được đánh số từ dưới lên là \(0,1,\ldots\). JOI-kun đang ở bậc \(0\) và muốn đi lên. Cậu có thể thực hiện hai loại hành động sau, nhưng không được đi xuống:

• Đi lên \(1\) bậc, mất \(A\) giây.
• Nhảy từ bậc hiện tại đến bậc cao hơn đúng \(D\) bậc, bỏ qua các bậc ở giữa, mất \(B\) giây.

Hiện có \(N\) công trình trên cầu thang. Công trình thứ \(i\) nằm trên các bậc \(L_i,L_i+1,\ldots,R_i\). JOI-kun không được đặt chân lên các bậc đang thi công.

Tháp có \(Q\) phòng được đánh số từ \(1\) đến \(Q\). Có thể vào phòng \(j\) từ bậc \(X_j\). Với mỗi phòng, JOI-kun muốn biết có thể tới được bậc đó hay không và, nếu có, thời gian ít nhất cần dùng.

Cho thông tin về JOI-kun, các công trình và các phòng, hãy trả lời yêu cầu trên với mọi \(1 \le j \le Q\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,Q\).
• Dòng thứ hai chứa ba số nguyên \(D,A,B\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(L_i,R_i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(X_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa thời gian ít nhất, tính bằng giây, để tới bậc \(X_j\) nếu có thể; nếu không thể, in -1.

Ràng buộc

• \(1 \le N \le 200000\).
• \(1 \le Q \le 200000\).
• \(1 \le D \le 10^{12}\).
• \(1 \le A \le 1000000\) và \(1 \le B \le 1000000\).
• \(1 \le L_i \le R_i \le 10^{12}\) với mọi \(1 \le i \le N\).
• \(R_i+1<L_{i+1}\) với mọi \(1 \le i \le N-1\).
• \(1 \le X_j \le 10^{12}\) với mọi \(1 \le j \le Q\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(R_i \le 1000000\) với mọi \(i\), \(X_j \le 1000000\) với mọi \(j\).
2. \(38\) điểm: \(N \le 2000\), \(Q \le 2000\).
3. \(25\) điểm: \(A=1\), \(B=D\).
4. \(32\) điểm: Không có ràng buộc bổ sung.

Ví dụ

3 1
4 10 35
4 5
10 12
14 14
13

120

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

6
11
17
22
-1
33
-1
44
-1
55

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2023/2024, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.