JOI 2018 - Worst Reporter 3
Xem PDFTrong lễ khai mạc IOI 2018, \(N\) thí sinh diễu hành thành một hàng dọc trên một trục số. Tất cả đều hướng về chiều dương. Tại thời điểm \(0\), thí sinh thứ \(i\) tính từ đầu hàng đứng ở tọa độ \(-i\). IOI-chan, người cầm cờ, đứng ở tọa độ \(0\).
Thí sinh thứ \(i\) có một giá trị gọi là độ chậm \(D_i\). Các thí sinh tuân theo quy tắc:
- Nếu khoảng cách từ thí sinh thứ \(i\) đến người ngay phía trước (một thí sinh khác hoặc IOI-chan) lớn hơn hoặc bằng \(D_i+1\), thí sinh thứ \(i\) lập tức di chuyển đến vị trí cách người đó đúng \(1\) đơn vị ở phía sau. Nếu chưa đủ khoảng cách này, thí sinh đứng yên.
IOI-chan di chuyển theo chiều dương với tốc độ \(1\) đơn vị khoảng cách trên mỗi đơn vị thời gian. Mỗi thí sinh di chuyển tức thời ngay khi điều kiện trên được thỏa mãn.
Bạn là phóng viên đưa tin về lễ khai mạc. Lẽ ra phải chụp ảnh, nhưng bạn lại ngủ suốt buổi lễ. Bạn đành chụp ảnh hội trường rồi vẽ thêm hình mọi người lên ảnh. Để không bị phát hiện, đồng thời ước lượng thời gian cần vẽ, bạn muốn trả lời \(Q\) câu hỏi: tại thời điểm \(T_j\), có bao nhiêu người đứng ở tọa độ thuộc đoạn \([L_j,R_j]\), kể cả hai đầu mút? Số người này bao gồm cả IOI-chan.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên \(N,Q\). \(N\) là số thí sinh, không tính IOI-chan.
- Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(D_i\).
- Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(T_j,L_j,R_j\) mô tả câu hỏi thứ \(j\).
Dữ liệu ra
In \(Q\) dòng. Dòng thứ \(j\) chứa đáp án của câu hỏi thứ \(j\).
Ràng buộc
- \(1 \le N \le 500\,000\).
- \(1 \le Q \le 500\,000\).
- \(1 \le D_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
- \(1 \le T_j \le 1\,000\,000\,000\) với \(1 \le j \le Q\).
- \(1 \le L_j \le R_j \le 1\,000\,000\,000\) với \(1 \le j \le Q\).
Phân nhóm
- \(7\) điểm: \(D_i=1\) với mọi \(1 \le i \le N\)
- \(12\) điểm: \(N \le 1\,000\); \(Q \le 1\,000\); \(T_j \le 1\,000\) và \(1 \le L_j \le R_j \le 1\,000\) với mọi \(1 \le j \le Q\)
- \(81\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
3 6
2
5
3
1 2 4
2 2 4
3 2 4
4 2 4
5 2 4
6 2 4Output
0
1
1
2
1
2Giải thích
Diễn biến của IOI-chan và các thí sinh như sau:
- Thời điểm \(0\): IOI-chan ở tọa độ \(0\); các thí sinh thứ \(1,2,3\) lần lượt ở \(-1,-2,-3\).
- Thời điểm \(1\): IOI-chan đến tọa độ \(1\). Không thí sinh nào di chuyển; các thí sinh vẫn ở \(-1,-2,-3\). Không có ai trong đoạn \([2,4]\), nên câu hỏi thứ nhất có đáp án \(0\).
- Thời điểm \(2\): IOI-chan đến tọa độ \(2\). Khoảng cách đến thí sinh thứ nhất đạt \(3\), nên thí sinh này đến tọa độ \(1\). Ba thí sinh ở \(1,-2,-3\). Chỉ IOI-chan nằm trong \([2,4]\), nên đáp án là \(1\).
- Thời điểm \(3\): IOI-chan đến tọa độ \(3\). Không thí sinh nào di chuyển; ba thí sinh ở \(1,-2,-3\). Chỉ IOI-chan nằm trong \([2,4]\), nên đáp án là \(1\).
- Thời điểm \(4\): IOI-chan đến tọa độ \(4\). Khoảng cách đến thí sinh thứ nhất đạt \(3\), nên thí sinh này đến tọa độ \(3\). Ba thí sinh ở \(3,-2,-3\). IOI-chan và thí sinh thứ nhất nằm trong \([2,4]\), nên đáp án là \(2\).
- Thời điểm \(5\): IOI-chan đến tọa độ \(5\). Không thí sinh nào di chuyển; ba thí sinh ở \(3,-2,-3\). Chỉ thí sinh thứ nhất nằm trong \([2,4]\), nên đáp án là \(1\).
- Thời điểm \(6\): IOI-chan đến tọa độ \(6\). Khoảng cách đến thí sinh thứ nhất đạt \(3\), nên thí sinh này đến tọa độ \(5\). Khi đó, khoảng cách từ thí sinh thứ nhất đến thí sinh thứ hai là \(7\), nên thí sinh thứ hai đến tọa độ \(4\). Tiếp theo, khoảng cách từ thí sinh thứ hai đến thí sinh thứ ba là \(7\), nên thí sinh thứ ba đến tọa độ \(3\). Ba thí sinh ở \(5,4,3\). Thí sinh thứ hai và thứ ba nằm trong \([2,4]\), nên đáp án là \(2\).
Ví dụ 2
Input
4 2
1
1
1
1
2 1 4
1 3 6Output
2
0Giải thích
Ví dụ này thỏa mãn các ràng buộc của nhóm 1.
Ví dụ 3
Input
6 6
11
36
28
80
98
66
36 29 33
190 171 210
18 20 100
1000 900 1100
92 87 99
200 100 300Output
1
6
0
5
2
7Nguồn
Kỳ thi:
- JOI 2018 Final Camp - Ngày 2 (4 Tháng 1., 2018)
Bình luận