trang chủ / đề bài / dimastair

Cầu thang và những chiếc hộp

Đề bài

Mô tả

Một cầu thang gồm n bậc, bậc thứ i có độ cao ai, với a1≤a2≤…≤an.

Lần lượt có m chiếc hộp hình chữ nhật được thả từ trên cao xuống cầu thang. Hộp thứ i có chiều rộng wi và chiều cao hi, được thả thẳng đứng phía trên wi bậc đầu tiên (tức là phủ các bậc 1,2,…,wi). Hộp rơi xuống cho đến khi đáy của nó chạm vào mặt trên của một bậc thang hoặc mặt trên của một hộp đã thả trước đó (trong phạm vi các bậc 1..wi). Chỉ tính việc chạm theo mặt nằm ngang: hộp có chiều rộng wi không chạm vào bậc wi+1. Hộp tiếp theo chỉ được thả sau khi hộp trước đã nằm yên.

Với mỗi hộp, hãy cho biết độ cao của đáy hộp sau khi nó dừng lại.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n, số bậc thang.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.
  • Dòng thứ ba chứa số nguyên m, số hộp.
  • m dòng tiếp theo, dòng thứ i chứa hai số nguyên wi và hi.

Dữ liệu ra

In ra m dòng, dòng thứ i là độ cao của đáy hộp thứ i sau khi dừng lại, theo đúng thứ tự thả.

Ràng buộc

  • 1≤n,m≤105
  • 1≤ai≤109, ai≤ai+1
  • 1≤wi≤n
  • 1≤hi≤109

Ví dụ

Input Output Giải thích
5
1 2 3 6 6
4
1 1
3 1
1 1
4 3
1
3
4
6
Hộp 1 nằm trên bậc 1 (độ cao 1), đỉnh ở độ cao 2. Hộp 2 phủ bậc 1..3, bậc 3 cao 3 nên đáy ở độ cao 3, đỉnh ở 4. Hộp 3 nằm trên hộp 2, đáy ở 4, đỉnh ở 5. Hộp 4 phủ bậc 1..4, bậc 4 cao 6 nên đáy ở 6.
3
1 2 3
2
1 1
3 1
1
3
Hộp 2 phủ cả 3 bậc, chạm bậc 3 ở độ cao 3 trước khi chạm hộp 1 (đỉnh ở độ cao 2).
1
1
5
1 2
1 10
1 10
1 10
1 10
1
3
13
23
33
Các hộp chồng lên nhau trên bậc duy nhất.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0