trang chủ / đề bài / icpc24_reg_l

Điều phối đường ray

Đề bài

Mô tả

Dooby là một người đam mê tàu hỏa, năng động và tỉ mỉ, vừa được tuyển làm nhân viên điều hành tàu. Tuy nhiên, nhiệm vụ đầu tiên của cô không hề đơn giản.

Dooby phụ trách một tuyến đường ray mới nối Primstation và Krustown. Đường ray là một đoạn thẳng dài s mét. Mỗi ngày, Dooby phải lập lịch chạy cho các đoàn tàu trên tuyến này, và danh sách tàu thay đổi theo từng ngày.

Ban đầu chưa có đoàn tàu nào. Công việc của Dooby kéo dài q ngày, vào ngày thứ i xảy ra một trong các sự kiện sau:

  • "+ wi vi": một đoàn tàu dài wi mét, chạy với vận tốc không đổi vi mét mỗi giờ được thêm vào danh sách tàu của Dooby.
  • "- wi vi": một đoàn tàu dài wi mét, chạy với vận tốc không đổi vi mét mỗi giờ bị xóa khỏi danh sách tàu của Dooby. Dữ liệu đảm bảo danh sách hiện tại có ít nhất một đoàn tàu như vậy.

Mỗi ngày, tất cả các đoàn tàu trong danh sách của Dooby đều xuất phát từ Primstation và phải đi đến Krustown. Vì chỉ có một đường ray, các đoàn tàu phải được sắp theo một thứ tự nhất định và xuất phát vào những thời điểm nhất định để không va chạm. Khi một đoàn tàu tới Krustown, nó lập tức được đưa vào nhà kho, nhường đường cho đoàn tàu tiếp theo.

Trước khi khởi hành, đầu tàu của mỗi đoàn tàu được đặt thẳng hàng với điểm đầu của đường ray. Một đoàn tàu được coi là đã tới Krustown khi đuôi tàu vượt qua điểm cuối của đường ray.

Để chứng tỏ năng lực, Dooby phải tìm thời điểm xuất phát của mọi đoàn tàu mỗi ngày sao cho:

  • không có hai đoàn tàu nào va chạm, và
  • thời gian ti cần để tất cả các đoàn tàu tới Krustown là nhỏ nhất.

Nhiệm vụ của bạn là giúp Dooby lập lịch. Với mỗi ngày trong q ngày, hãy tìm thời gian ti nhỏ nhất cần để tất cả các đoàn tàu đang có trong danh sách tới Krustown an toàn. In ti theo modulo 998244353.

Một cách hình thức, đặt M=998244353. Có thể chứng minh rằng đáp án biểu diễn được dưới dạng phân số tối giản pq, trong đó p,q là các số nguyên và q≢0(modM). Hãy in ra số nguyên bằng p·q−1modM, tức là số nguyên x thỏa 0≤x<M và x·q≡p(modM).

Điều kiện va chạm. Với đoàn tàu thứ i, gọi Reari(t) và Fronti(t) lần lượt là vị trí đuôi tàu và đầu tàu tại thời điểm t. Theo định nghĩa, Fronti(t)=Reari(t)+wi. Hai đoàn tàu i và j được coi là va chạm nếu tồn tại thời điểm t sao cho:

  • cả đoàn tàu i và đoàn tàu j đều đã rời Primstation (đã xuất phát),
  • cả hai đều chưa tới Krustown, và
  • min{Fronti(t),Frontj(t)}>max{Reari(t),Rearj(t)}.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên s và q (1≤s≤109, 1≤q≤200000): độ dài đường ray (mét) và số ngày làm việc của Dooby.

Mỗi dòng trong q dòng tiếp theo mô tả sự kiện của một ngày, có một trong hai dạng:

  • "+ wi vi" (1≤wi,vi≤106): thêm một đoàn tàu dài wi mét, vận tốc vi mét mỗi giờ vào danh sách.
  • "- wi vi" (1≤wi,vi≤106): xóa một đoàn tàu dài wi mét, vận tốc vi mét mỗi giờ khỏi danh sách. Dữ liệu đảm bảo danh sách hiện tại có ít nhất một đoàn tàu như vậy.

Dữ liệu ra

In ra q dòng. Dòng thứ i chứa thời gian nhỏ nhất cần để tất cả các đoàn tàu trong danh sách của ngày thứ i tới Krustown an toàn, theo modulo 998244353. Nếu ngày thứ i danh sách không có đoàn tàu nào, in ra 0.

Ràng buộc

  • 1≤s≤109
  • 1≤q≤200000
  • 1≤wi,vi≤106

Ví dụ

Input Output Giải thích
20 4
+ 2 2
+ 3 3
+ 5 2
- 2 2
11
12
499122191
499122190
Ngày 1: chỉ có tàu (2,2) (dài 2, vận tốc 2); đầu tàu tới Krustown sau 20/2=10 giờ, đuôi tàu ra khỏi đường ray thêm 2/2=1 giờ. Ngày 2: tàu (3,3) xuất phát lúc 413 giờ và tới Krustown đúng lúc 12 giờ; nếu xuất phát sớm hơn, ví dụ lúc 3 giờ, nó sẽ va chạm với tàu (2,2) lúc 7 giờ. Ngày 3: tàu (2,2) xuất phát lúc 0, tàu (5,2) lúc 1, tàu (3,3) lúc 656 giờ và tới nơi lúc 292 giờ; 499122191·2≡29(mod998244353). Ngày 4: tàu (3,3) xuất phát lúc 0, tàu (5,2) lúc 1 và tới nơi lúc 272 giờ.
10 6
+ 4 5
+ 6 5
- 4 5
- 6 5
+ 1 1
+ 1 1
399297744
4
598946615
0
11
12
Các đáp án lần lượt là 145,4,165,0,11,12 giờ. Ngày 4 danh sách rỗng nên in 0. Ngày 6 có hai đoàn tàu giống hệt nhau.

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