trang chủ / đề bài / icpc19_reg_b

Bài toán quả chuối

Đề bài

Mô tả

Gon đang chơi trò chơi "Những chú khỉ tham ăn".

Trò chơi được thiết lập như sau:

  • Có N cái thang, đánh số từ 1 đến N. Mỗi thang có chiều cao H và có H+1 bậc ở các độ cao 0,1,…,H. Ký hiệu (ℓ,h) là bậc ở độ cao h của thang thứ ℓ.
  • Có R sợi dây nằm ngang. Mỗi sợi dây nối hai bậc cùng độ cao của hai thang khác nhau. Các sợi dây được đánh số từ 1 đến R, sợi dây thứ i có độ dài bi. Không có sợi dây nào nối vào bậc 0 hay bậc H của bất kỳ thang nào. Mỗi bậc của một thang được nối với nhiều nhất một sợi dây.
  • Có B vị trí đặc biệt, đánh số từ 1 đến B. Vị trí thứ i được mô tả bởi 4 số nguyên ℓi,hi,xi,yi, với 1≤ℓi≤N và 1≤hi≤H. Với mọi số nguyên không âm t:

    • Tại thời điểm t·(xi+yi)+0.5, một quả chuối mới xuất hiện tại vị trí (ℓi,hi).
    • Tại thời điểm t·(xi+yi)+xi+0.5, quả chuối này biến mất khỏi vị trí (ℓi,hi).

    Ví dụ, nếu xi=2 và yi=3: một quả chuối xuất hiện lúc 0.5 và biến mất lúc 2.5; sau đó một quả chuối khác xuất hiện lúc 5.5 và biến mất lúc 7.5, và cứ thế. Đảm bảo không có sợi dây nào nối vào một vị trí đặc biệt, và các vị trí đặc biệt đôi một phân biệt.

Lúc bắt đầu trò chơi có N chú khỉ, đánh số từ 1 đến N. Chú khỉ thứ i đứng ở (i,0). Chú khỉ thứ i cần ci giây để leo lên một bậc của bất kỳ thang nào, và di giây để di chuyển một đơn vị độ dài dọc theo bất kỳ sợi dây nào.

Một chú khỉ ăn được một quả chuối khi và chỉ khi nó ở cùng vị trí với quả chuối và quả chuối chưa biến mất. Thời gian ăn chuối không đáng kể. Tất nhiên mỗi quả chuối chỉ được ăn một lần. Nếu nhiều chú khỉ cùng ở vị trí của một quả chuối tại cùng một thời điểm, chỉ một chú ăn được quả chuối đó. Tuy nhiên, nếu các chú khỉ tới một vị trí đặc biệt nhiều lần, chúng có thể ăn nhiều hơn một quả chuối ở vị trí này.

Người chơi điều khiển các chú khỉ. Vì Gon là một cậu bé đơn giản, cậu điều khiển các chú khỉ theo một chiến thuật rất đơn giản:

  • Nếu một chú khỉ đang ở một bậc thang có nối một sợi dây, và chú khỉ chưa từng đi trên sợi dây này theo bất kỳ chiều nào, nó lập tức đi dọc sợi dây sang đầu bên kia.
  • Ngược lại, chú khỉ leo lên trên thang.
  • Các chú khỉ luôn di chuyển theo hai quy tắc trên, cho tới khi không thể di chuyển được nữa (điều này chỉ xảy ra khi chúng tới bậc H của một thang nào đó).
  • Các chú khỉ có thể đi xuyên qua nhau.

Hỏi các chú khỉ ăn được bao nhiêu quả chuối nếu Gon làm theo chiến thuật này?

Dữ liệu vào

Dòng đầu tiên chứa 4 số nguyên N,H,R,B (1≤N≤3·105, 0≤R,B≤3·105, 1≤H≤109): số thang, chiều cao mỗi thang, số sợi dây và số vị trí đặc biệt.

Trong R dòng tiếp theo, dòng thứ i chứa 4 số nguyên bi,ℓ1,i,ℓ2,i,si (1≤bi≤104, 1≤ℓ1,i,ℓ2,i≤N, ℓ1,i≠ℓ2,i, 1≤si<H): sợi dây thứ i có độ dài bi và nối hai vị trí (ℓ1,i,si) và (ℓ2,i,si).

Trong N dòng tiếp theo, dòng thứ i chứa 2 số nguyên ci và di (1≤ci,di≤104): số giây để chú khỉ thứ i leo lên một bậc thang, và để di chuyển một đơn vị dọc theo một sợi dây.

Trong B dòng tiếp theo, dòng thứ i chứa 4 số nguyên ℓi,hi,xi,yi (1≤ℓi≤N, 1≤hi≤H, 1≤xi,yi≤104): (ℓi,hi) là vị trí đặc biệt thứ i, còn xi,yi là các tham số của nó.

Đảm bảo rằng:

  • Mỗi vị trí được nối với nhiều nhất một sợi dây.
  • Các vị trí đặc biệt (nơi chuối xuất hiện) đôi một phân biệt.
  • Các vị trí đặc biệt không được nối với sợi dây nào.

Dữ liệu ra

In ra một số nguyên là số quả chuối các chú khỉ ăn được khi làm theo chiến thuật của Gon.

Ràng buộc

  • 1≤N≤3·105, 0≤R,B≤3·105, 1≤H≤109
  • 1≤bi,ci,di,xi,yi≤104

Ví dụ

Input Output Giải thích
1 2 0 2
2 1000
1 1 1 2
1 2 2 1
1 Chỉ có 1 thang và không có dây; chú khỉ cần 2 giây để leo một bậc. Vị trí (1,1) có chuối từ 0.5 tới 1.5, từ 3.5 tới 4.5, ...; vị trí (1,2) có chuối từ 0.5 tới 2.5, từ 3.5 tới 5.5, ... Chú khỉ tới (1,1) lúc 2, khi đó không có chuối; tới (1,2) lúc 4 và ăn 1 quả chuối.
2 2 1 2
1 1 2 1
1 2
2 1
1 2 3 1
2 2 2 3
1 Dây nối (1,1) và (2,1), dài 1. Khỉ 1 ở (1,1) lúc 1, (2,1) lúc 3, (2,2) lúc 4. Khỉ 2 ở (2,1) lúc 2, (1,1) lúc 3, (1,2) lúc 5. Vị trí (1,2) có chuối từ 0.5 tới 3.5, từ 4.5 tới 7.5, ...; vị trí (2,2) có chuối từ 0.5 tới 2.5, từ 5.5 tới 7.5, ... Khỉ 2 ăn được chuối ở (1,2), khỉ 1 không ăn được quả nào.

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