Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

C11ANT2 - Vui đùa cùng Kiến

Trịnh là một học sinh giỏi trong lớp. Dù là một học sinh khá giỏi nhưng Trịnh luôn biết cách điều chỉnh thời khóa biểu của mình để cân bằng thời gian học và thời gian chơi thể thao vì Trịnh quan điểm rằng sức khỏe và kiến thức là hai yếu tố quan trọng để trở thành một người có ích cho xã hội. Mặc dù đã lên kế hoạch chơi thể thao nhưng dạo này thời tiết khá xấu, mưa liên miên đã cản trở các dự định rèn luyện thân thể của Trịnh.

Trong một lần bị bể kế hoạch do mưa quá to và gió giật rất mạnh nên Trịnh phải ngồi nhà. Lúc rãnh rỗi, Trịnh nghĩ rằng trời mưa thì sẽ có rất nhiều kiến nên cậu đã nghĩ ra trò chơi mới lạ với những con kiến. Cậu ta lấy một đoạn dây độ dài là X và bôi một lớp đường lên sợi dây và căng ra hai đầu. Sau đó, Trịnh chợp mắt một lát trong lúc chờ đợi lũ kiến bị dụ vào. Lúc tỉnh dậy, Trịnh đã thấy kiến bu đầy đoạn dây. Một số con đang đi về đầu mút bên phải của sợi dây. Các con kiến còn lại thì đang có hướng đi về đầu mút bên trái. Vì sợi dây khá mảnh nên trường hợp hai con kiến đứng cùng một chỗ sẽ không xảy ra. Trịnh đã đánh số các con kiến trên dây từ 1 -> N THEO MỘT THỨ TỰ LỘN XỘN và ghi lại vị trí của nó cũng như hướng di chuyển. Nếu con kiến thứ i đi tới một trong 2 đầu mút của sợi dây thì ngay sau đó no sẽ bị rớt ra khỏi đoạn dây. Trịnh muốn biết thời điểm mà con kiến thứ i đi tới một trong 2 đầu mút của sợi dây. Biết rằng các con kiến đi được 1 đơn vị trong một giây và nếu hai con kiến đụng nhau, chúng sẽ lập tức đổi hướng đi. Thời điểm 0 là thời điểm vị trí và hướng đi của các con kiên giống y như dữ liệu mà Trịnh đã ghi lại. Nói cách khác, thời điểm 0 là thời điểm Trịnh tỉnh dậy.

Dữ liệu vào

  • Dòng đầu chứa 2 số nguyên N, X.
  • Dòng thứ i trong N dòng tiếp theo chứa 2 số nguyên pos, dir. Trong đó pos là khoảng cách từ con kiến thứ i tới đầu mút bên trái của sợi dây và dir là hướng di chuyển của con kiến thứ i. Biến dir mang 2 giá trị là 0 và 1 tương ứng với hướng đi sang bên trái và hướng đi sang bên phải.

Dữ liệu ra

  • Gồm N dòng, dòng thứ i chứa thời điểm mà con kiến thứ i đi ra khỏi sợi dây.

Ràng buộc

 

  • 30% số test N ≤ 1000, X ≤ 1000.
  • 30% số test N ≤ 1000, X ≤ 109.
  • 40% số test N ≤ 106, X ≤ 109.

 

Ví dụ

Dữ liệu vào:
4 10
3 0
6 0
2 1
7 1

Dữ liệu ra:
6
8
3
3


Được gửi lên bởi:Nguyễn Duy Khánh
Ngày:2014-09-07
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOS round 26 - Sưu tầm

hide comments
2015-12-13 04:42:36 Nguyễn Thị Ngọc Lan
AMEN!!!
2015-11-23 14:57:08 sadasd
ôi đơn giản, Xử lý bit, kết hợp chặt tam phân, thêm cái cây BIT, persistencr segment tree, thêm cái Disjoint Set, tầm 400 dòng là AC
2015-07-06 17:15:03 Nắng
tks zeus :">
2015-04-13 14:18:08 [$Zeus$]
Chết với cái tội để cin cout :\ nộp 9 phát mới đc :v
2014-09-15 07:36:21 Stupid Dog
hoho
2014-09-15 07:36:04 Van Hac chuyen Sinh
hihi
2014-09-11 10:28:55 vn_army
Cần giải thích rõ về việc 2 con kiến "đụng nhau", do con kiến đi 1 đơn vị độ dài / s => nếu 2 con ở 2 vị trí liên tiếp thì sẽ tính là đụng nhau hay tính 0,5s sau mỗi con đi 0,5 đơn vị nữa sẽ đụng nhau.
2014-09-07 14:45:20 Skeleton Knight
thánh nghiêm túc: ích chứ sao lại ít
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.