trang chủ / đề bài / procqueue

Xử lý truy vấn

Đề bài

Mô tả

Một máy chủ đơn luồng cần xử lý n truy vấn. Truy vấn thứ i đến vào thời điểm ti và cần đúng di đơn vị thời gian để xử lý xong. Các thời điểm ti đôi một khác nhau và được cho theo thứ tự tăng dần.

Máy chủ có một hàng đợi chứa tối đa b truy vấn. Khi một truy vấn mới đến, máy chủ phản ứng theo đúng một trong ba cách sau:

  1. Nếu máy chủ đang rảnh và hàng đợi rỗng, truy vấn được bắt đầu xử lý ngay lập tức.
  2. Nếu máy chủ đang bận và hàng đợi có ít hơn b truy vấn, truy vấn mới được đưa vào cuối hàng đợi.
  3. Nếu máy chủ đang bận và hàng đợi đã có đủ b truy vấn, truy vấn mới bị từ chối và sẽ không bao giờ được xử lý.

Mỗi khi xử lý xong một truy vấn, máy chủ lập tức lấy truy vấn ở đầu hàng đợi ra xử lý tiếp (nếu hàng đợi không rỗng).

Nếu một truy vấn mới đến vào thời điểm x và máy chủ cũng vừa xử lý xong một truy vấn khác vào đúng thời điểm x, thì thứ tự được quy ước là: máy chủ lấy truy vấn từ hàng đợi ra trước, sau đó truy vấn mới mới được coi là đến.

Với mỗi truy vấn, hãy xác định thời điểm máy chủ xử lý xong nó, hoặc −1 nếu truy vấn đó bị từ chối.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên n và b: số truy vấn và sức chứa tối đa của hàng đợi.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên ti và di.

Dữ liệu ra

In ra n số nguyên e1,e2,…,en trên một dòng, trong đó ei là thời điểm máy chủ xử lý xong truy vấn thứ i, hoặc −1 nếu truy vấn thứ i bị từ chối.

Ràng buộc

  • 1≤n,b≤200000
  • 1≤ti,di≤109
  • ti−1<ti với mọi i>1

Ví dụ

Input Output Giải thích
4 1
2 8
4 8
10 9
15 2
10 18 27 -1 Truy vấn 1 đến lúc 2, máy rảnh nên chạy ngay và xong lúc 10. Truy vấn 2 đến lúc 4, máy bận, hàng đợi rỗng nên được xếp vào, chạy từ 10 đến 18. Truy vấn 3 đến lúc 10 đúng lúc máy xong truy vấn 1: theo quy ước, máy lấy truy vấn 2 ra trước nên hàng đợi rỗng trở lại, truy vấn 3 được xếp vào và chạy từ 18 đến 27. Truy vấn 4 đến lúc 15, máy vẫn bận và hàng đợi đã có truy vấn 3 (đủ b=1) nên bị từ chối.
5 1
2 9
4 8
10 9
15 2
19 1
11 19 -1 21 22 Truy vấn 1 chạy từ 2 đến 11, truy vấn 2 được xếp vào hàng đợi rồi chạy từ 11 đến 19. Lúc 10 truy vấn 3 đến khi máy còn bận và hàng đợi đã đủ 1 truy vấn nên bị từ chối. Truy vấn 4 đến lúc 15 và được xếp vào. Lúc 19 máy xong truy vấn 2 và truy vấn 5 cũng đến: máy lấy truy vấn 4 ra trước (chạy đến 21), nhờ vậy hàng đợi rỗng nên truy vấn 5 được xếp vào và chạy đến 22.

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