MINE - Đào vàng
Đề bài
Một nhóm nhân viên khai mỏ có dự định tiến vào một hầm mỏ dài và rất hẹp. Vì rất hẹp và dài, nên chỉ người vào cuối cùng mới có thể rời khỏi hầm mỏ. Ban đầu, hầm mỏ trống. Ở cửa hầm mỏ, chúng ta ghi lại thời gian một ai đó vào và ra hầm mỏ. Mỗi người thợ mỏ không được ở trong hầm mỏ quá m đơn vị thời gian. Hãy đếm xem có bao nhiêu tình huống khác nhau có thể xảy ra. Hai tình huống được xem là khác nhau, nếu tồn tại một thời điểm nào đó mà trong tình huống này, người i có trong hầm mỏ, trong tình huống khác, người i không có trong hầm mỏ. Các công nhân khai mỏ được đánh số từ 1 đến n. Công nhân khai mỏ thứ i không được vào hầm mỏ trước công nhân khai mỏ thứ i – 1(Công nhân 1 là người vào đầu tiên).
Dữ liệu vào
- Dòng đầu ghi hai số nguyên n và m, trong đó 1 ≤ n ≤ 2.10^5 và 1 ≤ m ≤ 10^6
- Dòng thứ hai ghi 2n số nguyên dương 1 ≤ a1 < a2 < … < a2n ≤ 10^6 là thời điểm (tính từ đầu ngày) có một người thợ mỏ vào hoặc ra hầm mỏ
Giới hạn:
- 10% số test có n ≤ 10
- 10% số test khác có n ≤ 200, m = 10^6
- 30% số test khác có n ≤ 200
- 40% số test khác có n ≤ 2000
- 10% số test còn lại không có ràng buộc gì thêm
Dữ liệu ra
- In ra kết quả sau khi chia dư cho 1000003
Ví dụ
Input 1
3 6 1 2 3 7 9 10
Output 1
2
các anh chị có thể chỉ em thuật toán bài này hoặc em xin tài liệu về dạng bài như này được không ạ? em có tra gg rồi nhưng không có ạ