trang chủ / đề bài / icpc25_mn_f

Hấp thụ sức mạnh

Đề bài

Mô tả

Bạn đang chơi một trò chơi điện tử Marvel rất nổi tiếng tên là Dr. Strange. Trong trò chơi này, bạn vào vai một siêu anh hùng cứu thế giới bằng cách hấp thụ sức mạnh của quái vật.

Cho danh sách n quái vật. Quái vật thứ i xuất hiện tại thời điểm Li và có mặt cho đến hết thời điểm Ri (tính cả Ri). Nó có mức sức mạnh Pi. Nhiều quái vật có thể có mặt cùng một lúc.

Để chiến đấu với quái vật, bạn sẽ thực hiện lần lượt m lượt hấp thụ sức mạnh. Trước lượt đầu tiên, bạn bắt đầu với giá trị sức mạnh đã hấp thụ Power0=1 (hấp thụ từ chính bạn). Với mỗi lượt j=1,2,…,m, năng lượng khả dụng Ej của bạn tại thời điểm đó được tính bởi:

Ej=1+(Dj·Powerj−1+Aj)modFj

Trong đó Dj là hệ số bền bỉ, Aj là hệ số nhanh nhẹn, Fj là mức mệt mỏi ở lượt j, và Powerj−1 là tổng sức mạnh của các quái vật đã hấp thụ ở lượt trước đó j−1.

Vì bạn là Dr. Strange, bạn có thể du hành xuyên thời gian. Tại thời điểm tj của lượt thứ j, với năng lượng Ej, bạn hấp thụ sức mạnh của Ej quái vật yếu nhất (có sức mạnh nhỏ nhất) đang có mặt. Nếu tại thời điểm đó có ít hơn Ej quái vật, bạn hấp thụ tất cả. Việc hấp thụ sức mạnh chỉ ảnh hưởng đến năng lượng của bạn, không làm yếu đi hay loại bỏ quái vật nào.

Gọi Powerj là tổng sức mạnh hấp thụ được trong lượt thứ j. Nhiệm vụ của bạn là xác định Power1,Power2,…,Powerm.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n, m: số quái vật và số lượt hấp thụ (1≤n,m≤105).
  • n dòng tiếp theo, mỗi dòng chứa ba số nguyên Li, Ri và Pi: thời điểm xuất hiện, thời điểm biến mất và sức mạnh của quái vật thứ i (1≤Li≤Ri≤105, 1≤Pi≤107).
  • m dòng tiếp theo, mỗi dòng chứa bốn số nguyên tj, Dj, Aj và Fj: thời điểm của lượt thứ j và các hệ số dùng để tính năng lượng của lượt này. Các tj tạo thành một hoán vị của các số từ 1 đến m (1≤tj≤m, 0≤Dj,Aj≤105, 1≤Fj≤105).

Dữ liệu ra

In ra m dòng, dòng thứ j chứa một số nguyên: tổng sức mạnh hấp thụ được trong lượt thứ j.

Ràng buộc

  • 1≤n,m≤105
  • 1≤Li≤Ri≤105, 1≤Pi≤107
  • t1,…,tm là một hoán vị của 1,…,m
  • 0≤Dj,Aj≤105, 1≤Fj≤105

Ví dụ

Input Output Giải thích
3 3
1 2 10
2 3 20
1 3 5
1 2 2 2
3 3 1 3
2 1 1 5
5
25
15
Lượt 1 tại t1=1 có hai quái vật. Power0=1 nên E1=1+(2×1+2)mod2=1, hấp thụ quái vật sức mạnh 5. Lượt 2: E2=1+(3×5+1)mod3=2, tổng 5+20=25. Lượt 3: E3=1+(1×25+1)mod5=2, hấp thụ hai quái vật sức mạnh 5 và 10, tổng 15.
4 3
1 3 4
2 2 4
1 1 7
3 3 1
2 0 2 3
3 4 5 6
1 1 0 4
8
5
11
Ví dụ bổ sung (không có trong đề gốc). Lượt 1: E1=3 nhưng tại thời điểm 2 chỉ có hai quái vật (sức mạnh 4 và 4), hấp thụ cả hai. Lượt 2: E2=1+37mod6=2, tại thời điểm 3 có quái vật 4 và 1. Lượt 3: E3=1+5mod4=2, tại thời điểm 1 có quái vật 4 và 7.

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