JOI-kun dự định tổ chức một sự kiện rút thăm sử dụng một số chẵn túi. Ban đầu, mỗi túi chứa một số bóng đỏ và một số bóng xanh; số bóng mỗi màu có thể bằng \(0\). Những người tham gia lần lượt đến cho tới khi có ít nhất một túi rỗng. Mỗi người rút một quả bóng từ mỗi túi. Nếu tổng số bóng đỏ và tổng số bóng xanh mà người đó rút được bằng nhau, người đó nhận một phần thưởng. Những quả bóng đã rút không được bỏ lại vào túi.

JOI-kun đã chuẩn bị \(N\) túi, đánh số từ \(0\) đến \(N-1\). Túi \(i\) (\(0\le i\le N-1\)) chứa \(X_i\) bóng đỏ và \(Y_i\) bóng xanh.

Sự kiện sẽ sử dụng một số túi trong số đó. Có \(Q\) phương án lựa chọn: phương án thứ \(j\) (\(1\le j\le Q\)) sử dụng các túi \(L_j,L_j+1,\ldots,R_j\), với \(R_j-L_j+1\) là số chẵn.

Để chuẩn bị phần thưởng, JOI-kun muốn biết tổng số phần thưởng lớn nhất mà những người tham gia có thể nhận trong từng phương án. Hãy viết chương trình nhận thông tin các túi và các phương án, rồi trả về giá trị này cho mỗi phương án. Các phương án được xét độc lập với số bóng ban đầu.

Chi tiết cài đặt

Nộp một tệp lottery.cpp, sử dụng chỉ thị #include "lottery.h" và cài đặt hai hàm:

void init(int N, int Q, std::vector<int> X, std::vector<int> Y);
int max_prize(int L, int R);

Hàm init được gọi đúng một lần khi bắt đầu. N là số túi JOI-kun chuẩn bị, Q là số phương án chọn túi. Hai mảng X, Y đều có độ dài \(N\); X[i], Y[i] lần lượt là số bóng đỏ và số bóng xanh trong túi \(i\) (\(0\le i\le N-1\)).

Hàm max_prize được gọi \(Q\) lần sau init. Ở lần gọi thứ \(j\) (\(1\le j\le Q\)), L và R lần lượt bằng \(L_j\) và \(R_j\). Hàm phải trả về tổng số phần thưởng lớn nhất mà những người tham gia có thể nhận trong phương án thứ \(j\).

Chương trình được phép định nghĩa các hàm phụ trợ và biến toàn cục. Chương trình không được sử dụng đầu vào chuẩn, đầ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.

Gói tệp hỗ trợ trong phần đính kèm chứa trình chấm mẫu grader.cpp, tệp tiêu đề, mã nguồn mẫu và các ví dụ. Đặt grader.cpp, lottery.cpp, lottery.h trong cùng thư mục, rồi biên dịch bằng:

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

Hoặc chạy ./compile.sh trong gói hỗ trợ. Khi biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

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

N Q
X_0 X_1 ... X_{N-1}
Y_0 Y_1 ... Y_{N-1}
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

Sau mỗi lần gọi max_prize, trình chấm mẫu xuất giá trị trả về trên một dòng của đầu ra chuẩn.

Ràng buộc

• \(2\le N\le 200\,000\).
• \(1\le Q\le 500\,000\).
• \(0\le X_i\le 10^9\) và \(0\le Y_i\le 10^9\) với \(0\le i\le N-1\).
• \(0\le L_j<R_j\le N-1\) với \(1\le j\le Q\).
• \(R_j-L_j+1\) là số chẵn với \(1\le j\le Q\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(16\) điểm: \(Q\le 100\); \(X_i\le 100\), \(Y_i\le 100\) với mọi \(0\le i\le N-1\); \(R_j-L_j+1\le 100\) với mọi \(1\le j\le Q\).
2. \(16\) điểm: \(Q\le 100\); \(R_j-L_j+1\le 100\) với mọi \(1\le j\le Q\).
3. \(19\) điểm: \(Q\le 200\,000\); \(L_j\le L_{j+1}\) và \(R_j\le R_{j+1}\) với mọi \(1\le j\le Q-1\).
4. \(12\) điểm: \(N\le 20\,000\), \(Q\le 50\,000\).
5. \(14\) điểm: \(N\le 100\,000\), \(Q\le 200\,000\).
6. \(23\) điểm: Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Ví dụ 1

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

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

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

2
0
2

Giải thích

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

Lần gọi max_prize đầu tiên sử dụng các túi \(0,1,2,3\). Có thể đạt tổng cộng \(2\) phần thưởng như sau:

• Người thứ nhất lần lượt rút bóng đỏ, xanh, đỏ, xanh từ các túi \(0,1,2,3\). Số bóng đỏ và xanh bằng nhau nên người đó nhận một phần thưởng.
• Người thứ hai lần lượt rút bóng xanh, đỏ, đỏ, xanh từ các túi \(0,1,2,3\). Số bóng đỏ và xanh bằng nhau nên người đó nhận một phần thưởng.
• Lúc này túi \(1\) rỗng và sự kiện kết thúc.

Không thể nhận nhiều hơn \(2\) phần thưởng, nên lời gọi đầu tiên phải trả về \(2\).

Lần gọi thứ hai sử dụng các túi \(1,2,3,4\). Túi \(4\) rỗng ngay từ đầu, nên sự kiện kết thúc trước khi có người rút bóng. Lời gọi thứ hai phải trả về \(0\).

Lần gọi thứ ba sử dụng các túi \(2,3\). Có thể đạt tổng cộng \(2\) phần thưởng như sau:

• Người thứ nhất rút một bóng đỏ từ túi \(2\) và một bóng đỏ từ túi \(3\). Số bóng hai màu không bằng nhau nên người đó không nhận phần thưởng.
• Người thứ hai rút một bóng đỏ từ túi \(2\) và một bóng xanh từ túi \(3\), nên nhận một phần thưởng.
• Người thứ ba rút một bóng đỏ từ túi \(2\) và một bóng xanh từ túi \(3\), nên nhận một phần thưởng.
• Lúc này cả hai túi \(2,3\) đều rỗng và sự kiện kết thúc.

Không thể nhận nhiều hơn \(2\) phần thưởng, nên lời gọi thứ ba phải trả về \(2\). Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4,5,6\).

Ví dụ 2

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

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

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

2
3
3
1
1

Giải thích

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

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Nguồn

JOI Open Contest 2025, bài Lottery, tác giả Riku Kawasaki.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.