trang chủ / đề bài / icpcwf24_j

Con đường tơ lụa... với robot!

Đề bài

Mô tả

Một phần của con đường tơ lụa cổ xưa từng đi qua miền nam Kazakhstan. Bạn đang mơ mộng về một con đường tơ lụa hiện đại với những đặc điểm riêng. Dọc theo con đường tưởng tượng này có các robot và các cửa hàng cất giữ tiền tenge (đơn vị tiền tệ quốc gia của Kazakhstan). Nếu một robot di chuyển tới vị trí có cửa hàng, robot đó sẽ thu toàn bộ số tenge của cửa hàng ấy cho bạn.

Chi phí di chuyển một robot là 1 tenge cho mỗi mét di chuyển. Vì vậy lợi nhuận khi đưa một robot tới một cửa hàng bằng số tenge mà cửa hàng đó đang giữ trừ đi số mét robot đã đi để tới được cửa hàng.

Xét kịch bản sau, kéo dài trong nhiều ngày. Ban đầu con đường trống, không có robot hay cửa hàng nào. Mỗi ngày, hoặc một robot mới, hoặc một cửa hàng mới được đặt tại một vị trí chưa có ai chiếm trên con đường. Ngay trước đó, mỗi cửa hàng đã có trên đường được bổ sung tenge để tổng số tiền của nó bằng đúng số tiền lúc nó mới được đặt lên đường, và mỗi robot được đưa về vị trí xuất phát ban đầu của nó.

Với mỗi ngày, hãy xác định lợi nhuận lớn nhất có thể thu được bằng cách di chuyển các robot để lấy tenge từ các cửa hàng. Lưu ý rằng không có hai robot nào xuất phát ở cùng một vị trí, nhưng chúng có thể ở cùng một vị trí trong khi di chuyển. Trong một ngày, mỗi cửa hàng chỉ có thể bị lấy hết tiền một lần.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên n (1≤n≤2·105), số ngày.

Tiếp theo là n dòng, dòng thứ i bắt đầu bằng số nguyên ti: ti=1 nếu ngày i có một robot mới được thêm vào, ti=2 nếu ngày đó có một cửa hàng mới được thêm vào. Tiếp theo là số nguyên xi (0≤xi≤108), vị trí của robot mới hoặc cửa hàng mới. Nếu ti=2, dòng đó còn chứa thêm số nguyên ci (0≤ci≤108), số tenge của cửa hàng. Mọi vị trí được cho đều đôi một khác nhau.

Dữ liệu ra

In ra n số nguyên, số thứ i là lợi nhuận lớn nhất có thể thu được sau ngày thứ i, mỗi số trên một dòng.

Ràng buộc

  • 1≤n≤2·105.
  • ti∈{1,2}, 0≤xi≤108, 0≤ci≤108.
  • Các xi đôi một khác nhau.

Ví dụ

Input Output Giải thích
6
1 20
2 15 15
2 40 50
1 50
2 80 20
2 70 30
0
10
35
50
50
60
Ngày 2: robot ở 20 đi tới 15, lời 15−5=10. Ngày 3: robot đi sang trái tới 15 rồi quay lại sang phải tới 40, đi 5+25=30 mét, thu 65, lời 35. Ngày 4: robot ở 20 lấy cửa hàng ở 15 (lời 10), robot ở 50 lấy cửa hàng ở 40 (lời 40). Ngày 6: robot ở 50 đi sang trái tới 40 rồi sang phải tới 80 (đi 50 mét, thu 100), robot ở 20 lấy cửa hàng ở 15, tổng lời 60.
5
1 70000000
2 100000000 40000000
2 20000000 30000000
2 60000000 100000000
2 90000000 90000000
0
10000000
10000000
90000000
180000000
Ngày 5: robot đi sang trái tới 6·107 rồi quay sang phải tới 108, đi 5·107 mét và thu 2,3·108 tenge. Cửa hàng ở 2·107 ở quá xa nên không đáng lấy.

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