JOI 2019 - Trại huấn luyện, ngày 2

Có \(N\) ăng-ten, đánh số từ \(1\) đến \(N\), nằm trên một đường thẳng theo thứ tự đó. Khoảng cách giữa hai ăng-ten liên tiếp là \(1\) km. Ăng-ten \(i\) có độ cao \(H_i\) và có thể gửi thông tin đến những ăng-ten cách nó từ \(A_i\) đến \(B_i\) km, kể cả hai đầu mút.

Hai ăng-ten \(x,y\) với \(1\le x<y\le N\) liên lạc được với nhau khi và chỉ khi cả hai đều gửi thông tin được cho nhau. Chi phí liên lạc của cặp đó là \(|H_x-H_y|\).

Thủ tướng K của nước JOI nhận được \(Q\) phản ánh về kết nối kém. Với phản ánh thứ \(j\), sự cố nằm trong các ăng-ten \(L_j,L_j+1,\ldots,R_j\). Hãy xác định có cặp ăng-ten nào liên lạc được với nhau trong đoạn đó hay không; nếu có, tìm chi phí liên lạc lớn nhất của một cặp như vậy.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N
H_1 A_1 B_1
...
H_N A_N B_N
Q
L_1 R_1
...
L_Q R_Q

Tất cả dữ liệu vào là số nguyên.

Dữ liệu ra

Ghi \(Q\) dòng. Dòng thứ \(j\) ghi -1 nếu không có cặp ăng-ten nào liên lạc được với nhau trong đoạn \([L_j,R_j]\); ngược lại, ghi chi phí liên lạc lớn nhất của một cặp trong đoạn đó.

Ràng buộc

• \(2\le N\le200\,000\).
• \(1\le H_i\le10^9\) với \(1\le i\le N\).
• \(1\le A_i\le B_i\le N-1\) với \(1\le i\le N\).
• \(1\le Q\le200\,000\).
• \(1\le L_j<R_j\le N\) với \(1\le j\le Q\).

Phân nhóm

1. (2 điểm) \(N\le300\) và \(Q\le300\).
2. (11 điểm) \(N\le2000\).
3. (22 điểm) \(Q=1\), \(L_1=1\), \(R_1=N\).
4. (65 điểm) Không có ràng buộc bổ sung.

Ví dụ

5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

-1
1
8
8
99

20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20

806460109

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 2. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.

Đầu bếp Bitaro tham gia một cuộc thi nấu ăn. Anh phải hoàn thành hai món: cơm tô IOI và cà ri JOI.

Món cơm tô IOI gồm \(N\) bước. Bước thứ \(i\) mất đúng \(A_i\) phút. Ban đầu chỉ có thể thực hiện bước thứ nhất; muốn thực hiện bước thứ \(i\ge2\), phải hoàn thành bước thứ \(i-1\) trước.

Món cà ri JOI gồm \(M\) bước. Bước thứ \(j\) mất đúng \(B_j\) phút. Các bước của món này cũng phải thực hiện theo thứ tự từ \(1\) đến \(M\).

Mỗi bước đòi hỏi sự tập trung: một khi bắt đầu một bước, Bitaro không thể làm bước khác trước khi hoàn thành bước đó. Anh có thể đổi món giữa hai bước. Kể từ khi cuộc thi bắt đầu, anh không được nghỉ cho đến khi hoàn thành cả hai món.

Điểm nghệ thuật được tính như sau:

• Nếu hoàn thành bước thứ \(i\) của món cơm tô IOI trong vòng \(S_i\) phút kể từ lúc bắt đầu cuộc thi, Bitaro nhận \(P_i\) điểm. \(P_i\) có thể âm.
• Nếu hoàn thành bước thứ \(j\) của món cà ri JOI trong vòng \(T_j\) phút kể từ lúc bắt đầu cuộc thi, Bitaro nhận \(Q_j\) điểm. \(Q_j\) có thể âm.

Hoàn thành đúng thời hạn vẫn được tính điểm; nếu hoàn thành muộn hơn thời hạn, bước đó không đem lại điểm. Hãy tìm tổng điểm nghệ thuật lớn nhất Bitaro có thể đạt được.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N M
A_1 S_1 P_1
...
A_N S_N P_N
B_1 T_1 Q_1
...
B_M T_M Q_M

Tất cả dữ liệu vào là số nguyên.

Dữ liệu ra

Ghi một dòng chứa tổng điểm nghệ thuật lớn nhất có thể đạt được.

Ràng buộc

• \(1\le N,M\le1\,000\,000\).
• \(1\le A_i\le10^9\) với \(1\le i\le N\).
• \(1\le B_j\le10^9\) với \(1\le j\le M\).
• \(1\le S_i\le2\times10^{15}\) với \(1\le i\le N\).
• \(1\le T_j\le2\times10^{15}\) với \(1\le j\le M\).
• \(-10^9\le P_i\le10^9\) với \(1\le i\le N\).
• \(-10^9\le Q_j\le10^9\) với \(1\le j\le M\).

Phân nhóm

1. (5 điểm) \(N,M\le200\,000\) và \(S_1=\cdots=S_N=T_1=\cdots=T_M\).
2. (3 điểm) \(N,M\le12\) và \(P_i=Q_j=1\) với mọi \(i,j\).
3. (7 điểm) \(N,M\le2000\) và \(P_i=Q_j=1\) với mọi \(i,j\).
4. (39 điểm) \(N,M\le200\,000\) và \(P_i=Q_j=1\) với mọi \(i,j\).
5. (11 điểm) \(N,M\le200\,000\), \(P_i\ge1\) và \(Q_j\ge1\) với mọi \(i,j\).
6. (9 điểm) \(P_i\ge1\) và \(Q_j\ge1\) với mọi \(i,j\).
7. (17 điểm) \(N,M\le200\,000\).
8. (9 điểm) Không có ràng buộc bổ sung.

Ví dụ

4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1

6

5 7
16 73 16
17 73 10
20 73 1
14 73 16
18 73 10
3 73 2
10 73 7
16 73 19
12 73 4
15 73 15
20 73 14
15 73 8

63

9 11
86 565 58
41 469 -95
73 679 28
91 585 -78
17 513 -63
48 878 -66
66 901 59
72 983 -70
68 1432 11
42 386 -87
36 895 57
100 164 10
96 812 -6
23 961 -66
54 193 51
37 709 82
62 148 -36
28 853 22
15 44 53
77 660 -19

99

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 2. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.

Nước JOI có \(N\) thành phố, đánh số từ \(0\) đến \(N-1\). Có \(A\) tuyến đường sắt, đánh số từ \(0\) đến \(A-1\). Tuyến thứ \(i\) nối hai chiều giữa \(U_i\) và \(V_i\), với giá vé \(C_i\). Các tuyến đường sắt nối các cặp thành phố khác nhau.

Cũng có \(B\) tuyến xe buýt, đánh số từ \(0\) đến \(B-1\). Tuyến thứ \(j\) nối hai chiều giữa \(S_j\) và \(T_j\), với giá vé \(D_j\). Các tuyến xe buýt nối các cặp thành phố khác nhau. Một tuyến đường sắt và một tuyến xe buýt có thể nối cùng một cặp thành phố. Có thể đi giữa bất kỳ hai thành phố nào bằng đường sắt và/hoặc xe buýt.

Azer muốn biết tổng giá vé nhỏ nhất để đi từ thành phố \(0\) đến từng thành phố. Azer chỉ biết các tuyến đường sắt, còn Baijan chỉ biết các tuyến xe buýt. Hai người trao đổi các ký tự 0 hoặc 1, với tổng số ký tự cả hai gửi không quá \(58\,000\).

Hãy cài đặt chương trình cho cả Azer và Baijan để sau khi trao đổi, Azer tìm được các giá trị cần thiết.

Giao diện tương tác

Nộp một tệp C++ cài đặt cả hai phần Azer và Baijan, khai báo #include "transportations.h". Không cài đặt hàm main. Phần Azer gồm các hàm:

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C);
void ReceiveA(bool x);
std::vector<int> Answer();

• InitA được gọi đúng một lần lúc bắt đầu. \(N\) là số thành phố, \(A\) là số tuyến đường sắt. Các mảng U, V, C có độ dài \(A\), mô tả hai đầu mút và giá vé của từng tuyến.
• ReceiveA(x) được gọi mỗi khi Azer nhận một ký tự từ Baijan; true biểu diễn 1, false biểu diễn 0.
• Answer() được gọi đúng một lần khi tất cả ký tự đã được nhận. Hàm phải trả về mảng Z có độ dài \(N\), nếu không nhận Wrong Answer [1]. Z[k] phải là tổng giá vé nhỏ nhất từ thành phố \(0\) đến thành phố \(k\); đặc biệt Z[0] = 0.

Trong phần Azer, có thể gọi hàm do thư viện cung cấp để gửi một ký tự cho Baijan:

void SendA(bool y);

Trong cùng tệp nộp, cài đặt phần Baijan gồm các hàm:

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D);
void ReceiveB(bool y);

• InitB được gọi đúng một lần lúc bắt đầu. \(N\) là số thành phố, \(B\) là số tuyến xe buýt. Các mảng S, T, D có độ dài \(B\), mô tả hai đầu mút và giá vé của từng tuyến.
• ReceiveB(y) được gọi mỗi khi Baijan nhận một ký tự từ Azer; true biểu diễn 1, false biểu diễn 0.

Trong phần Baijan, có thể gọi hàm do thư viện cung cấp để gửi một ký tự cho Azer:

void SendB(bool x);

Thứ tự trao đổi

Với mỗi test, trình chấm tạo hai hàng đợi: \(Q_Y\) chứa các ký tự Azer gửi và \(Q_X\) chứa các ký tự Baijan gửi. Trước tiên, gọi InitA, rồi InitB; các ký tự gửi trong hai hàm này được đưa vào hàng đợi tương ứng.

• Nếu ít nhất một hàng đợi không rỗng, lấy một ký tự ở đầu hàng đợi đó và gọi ReceiveA hoặc ReceiveB tương ứng. Nếu cả hai hàng đợi đều không rỗng, không quy định bên nào được nhận trước.
• Khi SendA được gọi trong ReceiveA, ký tự gửi được đưa vào \(Q_Y\).
• Khi SendB được gọi trong ReceiveB, ký tự gửi được đưa vào \(Q_X\).
• Khi cả hai hàng đợi đều rỗng, gọi Answer rồi kết thúc chương trình.

Tổng số lần gọi SendA và SendB không được vượt quá \(58\,000\), nếu không nhận Wrong Answer [2].

Có thể khai báo biến toàn cục và hàm phụ. Tệp nộp được biên dịch cùng trình chấm thành một tệp thực thi. Nên đặt biến và hàm phụ của hai bên trong các namespace khác nhau để tránh trùng tên, còn các hàm giao diện ở trên phải được khai báo ở phạm vi toàn cục. Đặt các chỉ thị #include ngoài namespace. Khi chấm thực tế, cùng tệp thực thi được chạy thành hai tiến trình riêng cho Azer và Baijan, không chia sẻ biến toàn cục. Tiến trình Azer chỉ nhận dữ liệu đường sắt và được gọi các hàm của Azer; tiến trình Baijan chỉ nhận dữ liệu xe buýt và được gọi các hàm của Baijan.

Không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Thư viện thử nghiệm

Gói tệp mẫu chứa transportations.h, transportations.cpp, grader.cpp và README.txt. Tệp README.txt giải thích cách chuyển từ giao diện hai tệp của đề gốc sang giao diện một tệp nộp. Đặt ba tệp mã nguồn và tiêu đề trong cùng thư mục, thay nội dung transportations.cpp bằng lời giải của bạn và biên dịch bằng:

g++ -std=gnu++14 -O2 -o grader grader.cpp transportations.cpp

Trình chấm mẫu chạy trong một tiến trình, khác với trình chấm thực tế.

Dữ liệu vào

Đầu vào của trình chấm mẫu có dạng:

N A B
U_0 V_0 C_0
...
U_{A-1} V_{A-1} C_{A-1}
S_0 T_0 D_0
...
S_{B-1} T_{B-1} D_{B-1}

Nếu \(A=0\) hoặc \(B=0\), phần tương ứng không có dòng nào.

Dữ liệu ra

Theo mô tả trong đề chính thức, trình chấm mẫu ghi loại lỗi Wrong Answer [1] hoặc Wrong Answer [2] ra đầu ra lỗi chuẩn và không ghi gì ra đầu ra chuẩn nếu có lỗi. Nếu không, nó ghi Accepted: L ra đầu ra lỗi chuẩn, trong đó \(L\) là tổng số ký tự đã gửi, và ghi mảng trả về ra đầu ra chuẩn, mỗi phần tử một dòng:

Z[0]
...
Z[N-1]

Trình chấm mẫu không kiểm tra các giá trị trong Z có đúng hay không. Nếu có nhiều loại lỗi, chỉ một loại được báo.

Ràng buộc

• \(1\le N\le2000\).
• \(0\le A,B\le500\,000\).
• \(0\le U_i,V_i\le N-1\) và \(U_i\ne V_i\) với \(0\le i<A\).
• Hai tuyến đường sắt khác nhau không nối cùng một cặp thành phố, kể cả khi đảo thứ tự hai đầu mút.
• \(0\le S_j,T_j\le N-1\) và \(S_j\ne T_j\) với \(0\le j<B\).
• Hai tuyến xe buýt khác nhau không nối cùng một cặp thành phố, kể cả khi đảo thứ tự hai đầu mút.
• Có thể đi giữa mọi cặp thành phố bằng đường sắt và/hoặc xe buýt.
• \(1\le C_i\le500\) với \(0\le i<A\).
• \(1\le D_j\le500\) với \(0\le j<B\).

Phân nhóm

1. (6 điểm) \(A=0\).
2. (8 điểm) \(B\le1000\).
3. (8 điểm) \(A+B=N-1\).
4. (38 điểm) \(N\le900\).
5. (14 điểm) \(N\le1100\).
6. (10 điểm) \(N\le1400\).
7. (16 điểm) Không có ràng buộc bổ sung.

Ví dụ giao tiếp

4 3 4
0 1 6
2 1 4
2 0 10
1 2 3
3 1 1
3 2 3
3 0 7

Một chuỗi lời gọi tương ứng:

Nguồn

JOI 2018/2019 Spring Training Camp, ngày 2. Đề gốc tiếng Anh, do Japanese Committee for the International Olympiad in Informatics công bố. Bản dịch tiếng Việt theo CC BY-SA 4.0.