AO LÀNG S2 LẦN II - Thăng cấp
Xem dạng PDFChủ đề vẫn là con game Arknights mà Loli đang chơi.
Arknights có rất nhiều màn chơi. Ta có thể đơn giản hóa rằng, tựa game này có ~n~ màn chơi tất cả. Mỗi màn chơi sẽ yêu cầu người chơi phải có cấp độ không dưới cấp độ mà màn chơi yêu cầu. Gọi cấp độ tối thiểu để chơi màn chơi thứ ~i~ là ~h_i~.
Các màn chơi sẽ càng ngày càng khó, đòi hỏi người chơi phải có cấp độ càng ngày càng cao. Nói cách khác, ta có ~h_i \le h_{i+1}~ với mọi ~i < n~.
Do Loli rất yêu tựa game này nên Loli lập ra ~q~ tài khoản, mỗi tài khoản được đánh số thứ tự từ ~1~ đến ~q~. Hiện tại cấp độ tài khoản thứ ~i~ của Loli là ~x_i~, và Loli muốn biết rằng, nếu hắn cố gắng lên thêm ~y_i~ cấp độ nữa ở tài khoản này, thì hắn sẽ qua được thêm bao nhiêu màn chơi?
Input
Lấy từ tệp THANGCAP.INP gồm:
- Dòng đầu tiên chứa một số nguyên dương ~n~ ~(1\le n\le 5\times 10^5)~ là số màn chơi.
- Dòng thứ hai chứa ~n~ số nguyên dương ~h_i~ ~(1\le h_i\le 2\times 10^9)~ là cấp độ tối thiểu để chơi màn chơi thứ ~i~.
- Dòng thứ ba chứa số nguyên dương ~q~ ~(1\le q \le 10^5)~ là số tài khoản của Loli.
- ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x_i~ và ~y_i~ ~(1\le x_i, y_i \le 10^9)~ thể hiện câu hỏi của Loli ở tài khoản thứ ~i~.
Output
Ghi ra tệp THANGCAP.OUT gồm:
- ~q~ dòng, dòng thứ ~i~ chứa một số nguyên tương ứng với số màn chơi có thể qua được thêm sau khi thăng cấp ở tài khoản thứ ~i~.
Sample Input 1
5
2 6 7 10 15
3
1 3
7 8
5 20
Sample Output 1
1
2
4
Giải thích
- Ở tài khoản thứ ~1~, Loli thăng cấp từ cấp ~1~ lên cấp ~1+3=4~, qua thêm được màn chơi thứ ~1~.
- Ở tài khoản thứ ~2~, Loli thăng cấp từ cấp ~7~ lên cấp ~7+8=15~, qua thêm được ~2~ màn chơi là màn thứ ~4~ và ~5~.
- Ở tài khoản thứ ~3~, Loli thăng cấp từ cấp ~5~ lên cấp ~5+20=25~, qua thêm được ~4~ màn chơi từ màn thứ ~2~ đến màn thứ ~5~.
Ràng buộc
- ~40\%~ test có ~q\times n \le 10^8~;
- ~60\%~ test còn lại không có ràng buộc gì thêm.
Bình luận
sigma boi
voãi A9 :)))