JOI 2021 - Event Hopping
Xem PDFNước IOI có hai thị trấn, được đánh số \(1\) và \(2\). Tổng cộng có \(N\) sự kiện được tổ chức tại hai thị trấn, đánh số từ \(1\) đến \(N\). Sự kiện \(i\) (\(1 \le i \le N\)) diễn ra tại thị trấn \(P_i\), từ thời điểm \(S_i+0.1\) đến thời điểm \(S_i+0.9\), trong đó \(S_i\) là số nguyên. Để tham gia sự kiện \(i\), JOI phải ở thị trấn \(P_i\) trong toàn bộ khoảng thời gian từ \(S_i+0.1\) đến \(S_i+0.9\).
JOI quyết định đi tham gia các sự kiện. JOI có thể tham gia một số sự kiện và di chuyển giữa hai thị trấn khi cần. Hành trình bắt đầu tại thời điểm \(0\), ở một trong hai thị trấn do JOI tùy ý chọn.
JOI có thể di chuyển giữa hai thị trấn theo cả hai chiều. Gọi \(j\) là số sự kiện JOI đã tham gia trước thời điểm bắt đầu một lần di chuyển. Thời gian cần cho lần di chuyển đó là \(D+K \times j\).
Cho thông tin về các sự kiện và việc di chuyển, hãy viết chương trình tìm số sự kiện nhiều nhất mà JOI có thể tham gia.
Dữ liệu vào
Dòng thứ nhất chứa ba số nguyên \(N, D, K\).
Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(P_i, S_i\), cách nhau bởi dấu cách.
Dữ liệu ra
In ra trên một dòng số sự kiện nhiều nhất mà JOI có thể tham gia.
Ràng buộc
- \(1 \le N \le 200\,000\).
- \(1 \le D \le 10^{12}\).
- \(0 \le K \le 10^{12}\).
- \(1 \le P_i \le 2\) với mọi \(1 \le i \le N\).
- \(1 \le S_i \le 10^{12}\) với mọi \(1 \le i \le N\).
- \(S_i \ne S_j\) với mọi \(1 \le i < j \le N\).
- Tất cả các giá trị đầu vào đều là số nguyên.
Phân nhóm
Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.
- (8 điểm) \(K=0\), \(N \le 20\).
- (11 điểm) \(K=0\), \(N \le 4000\).
- (24 điểm) \(K=0\).
- (12 điểm) \(N \le 160\).
- (23 điểm) \(N \le 4000\).
- (22 điểm) Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
5 3 0
1 1
1 2
1 10
2 5
2 6Output
4Giải thích
Chẳng hạn, JOI có thể tham gia \(4\) sự kiện theo hành trình sau:
- Tại thời điểm \(0\), JOI ở thị trấn \(1\).
- Từ thời điểm \(1.1\) đến \(1.9\), tham gia sự kiện \(1\) ở thị trấn \(1\).
- Từ thời điểm \(2.1\) đến \(2.9\), tham gia sự kiện \(2\) ở thị trấn \(1\).
- Từ thời điểm \(3\) đến \(6\), di chuyển từ thị trấn \(1\) đến thị trấn \(2\), mất \(3 = D+K \times 2\) đơn vị thời gian.
- Từ thời điểm \(6.1\) đến \(6.9\), tham gia sự kiện \(5\) ở thị trấn \(2\).
- Từ thời điểm \(7\) đến \(10\), di chuyển từ thị trấn \(2\) đến thị trấn \(1\), mất \(3 = D+K \times 3\) đơn vị thời gian.
- Từ thời điểm \(10.1\) đến \(10.9\), tham gia sự kiện \(3\) ở thị trấn \(1\).
Không có cách nào tham gia từ \(5\) sự kiện trở lên, nên in ra \(4\).
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 4, 5, 6\).
Ví dụ 2
Input
7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25Output
6Giải thích
Chẳng hạn, JOI có thể tham gia \(6\) sự kiện theo hành trình sau:
- Tại thời điểm \(0\), JOI ở thị trấn \(2\).
- Từ thời điểm \(2.1\) đến \(2.9\), tham gia sự kiện \(1\) ở thị trấn \(2\).
- Từ thời điểm \(3\) đến \(8\), di chuyển từ thị trấn \(2\) đến thị trấn \(1\), mất \(5 = D+K \times 1\) đơn vị thời gian.
- Từ thời điểm \(8.1\) đến \(8.9\), tham gia sự kiện \(2\) ở thị trấn \(1\).
- Từ thời điểm \(11.1\) đến \(11.9\), tham gia sự kiện \(4\) ở thị trấn \(1\).
- Từ thời điểm \(12\) đến \(23\), di chuyển từ thị trấn \(1\) đến thị trấn \(2\), mất \(11 = D+K \times 3\) đơn vị thời gian.
- Từ thời điểm \(23.1\) đến \(23.9\), tham gia sự kiện \(5\) ở thị trấn \(2\).
- Từ thời điểm \(24.1\) đến \(24.9\), tham gia sự kiện \(6\) ở thị trấn \(2\).
- Từ thời điểm \(25.1\) đến \(25.9\), tham gia sự kiện \(7\) ở thị trấn \(2\).
Không có cách nào tham gia từ \(7\) sự kiện trở lên, nên in ra \(6\).
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(4, 5, 6\).
Ví dụ 3
Input
12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768Output
8Giải thích
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 4, 5, 6\).
Ví dụ 4
Input
15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575Output
11Giải thích
Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(4, 5, 6\).
Nguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.
Kỳ thi:
- JOI 2021 - Vòng loại 2 (13 Tháng 12., 2020)
Bình luận