USACO 2019 - Dec - Silver - Meetings

Xem dạng PDF

Gửi bài giải

Điểm: 0,20 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
http://www.usaco.org/index.php?page=viewproblem2&cpid=967
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hai trang trại nằm trên vị trí ~0~ và ~L (1 \leq L \leq 10^9)~ trên trục số. Có ~N~ con bò ~(1 \leq L \leq 5*10^4)~ nằm trên các vị trí phân biệt trên trục số này. Ban đầu, con bò thứ i nằm ở vị trí ~x_i~ và di chuyển theo chiều dương hoặc âm với vận tốc 1 đơn vị 1 giây, được thể hiện bằng số nguyên ~d_i~ có giá trị bằng ~1~ hoặc ~-1~. Mỗi con bò cũng có cân nặng ~w_i~ trong khoảng ~[1,10^3]~. Mỗi con bò di chuyển với vận tốc không đổi cho đến một trong những việc sau diễn ra:

  • Nếu con bò thứ ~i~ tới được trang trại, thì con bò thứ ~i~ dừng di chuyển.

  • Một cuộc va chạm gặp diễn ra khi 2 con bò ~i~ và ~j~ chiếm cùng mỗi điểm, điểm đó không phải trang trại. Trong trường hợp nó, bò ~i~ sẽ được gán vận tốc của bò ~j~ và ngược lại. Lưu ý rằng những con bò có thể gặp tại điểm không nguyên.

Gọi ~T~ là thời điểm sớm nhất mà tổng khối lượng của những con bò đã dừng (do đã tới trang trại) bằng ít nhất một nửa tổng khối lượng của những con bò. Hãy xác định tổng số va chạm trong khoảng thời gian ~0…T~ (tính cả ~T~).

Input

Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~L~, cách bởi ~1~ dấu cách.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên ~w_i~, ~x_i~, và ~d_i~. Mọi ~x_i~ đều phân biệt và thỏa mãn ~ 0 \lt x_i \lt L~

Output

In ra số lượng va chạm.

Sample Input

3 5
1 1 1
2 2 -1
3 3 -1

Sample Output

2

Giải thích

Những con bò di chuyển theo các bước sau:

  1. Bò thứ nhất và thứ hai gặp nhau tại vị trí 1.5 vào thời điểm 0.5. Bò thứ nhất hiện có vận tốc là −1 và bò thứ hai có vận tốc là 1.
  2. Bò thứ hai và bò thứ ba gặp nhau gặp nhau tại vị trí thứ 2 vào thời điểm 1. Bò thứ hai hiện có vận tốc là −1 và bò thứ ba có vận tốc là 1.
  3. Bò thứ nhất sẽ tới được trang trại bên trái vào thời điểm 2.
  4. Bò thứ hai tới được trang trại bên trái vào thời điểm 3.
  5. Quá trình kết thúc do tổng khối lượng của bò đã tới trang trại đã bằng ít nhất một nửa tổng khối lượng tất cả các con bò. Tổng cộng đã có 2 va chạm.

Subtask

  • Test 1 là test ví dụ
  • Test 2-4 có giới hạn ~N \le 10^2~ và ~w_i=1~ với mọi ~i~
  • Test 5-7 có giới hạn ~N \le 10^2~ và ~w_i=1~ với mọi ~i~
  • Các test còn lại không có giới hạn gì thêm.

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.