Bedao Mini Contest 24 - Reverse Cow
View as PDF
Cho một đàn bò đánh số theo thứ tự từ ~1~ đến ~n~. Hàng ngày, sẽ có ~k~ sự kiện diễn ra theo thứ tự, sự kiện thứ ~i~ sẽ đảo ngược vị trí các con bò trong đoạn ~[l_i, r_i]~.
Biết rằng ~k~ sự kiện đó hàng ngày đều được diễn ra như nhau. Hãy xác định vị trí từng con bò sau ~d~ ngày.
Input
Dòng đầu gồm ba số nguyên dương ~n~, ~k~ và ~d~ (~1 \leq n \leq 10^5, 1 \leq k \leq 100, 1 \leq d \leq 2 \cdot 10^9~).
~k~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~l_i~, ~r_i~ tương ứng với việc đảo ngược vị trí các con bò trong đoạn ~l_i, r_i~ ~(1 \le l_i \le r_i \le n)~.
Output
- Gồm một dòng gồm ~n~ số nguyên dương, số thứ ~i~ ghi ra số thứ tự của con bò tại vị trí ~i~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10\%~ | ~k \cdot d \le 100~ |
| 2 | ~20\%~ | ~d \le 100~ |
| 3 | ~70\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
4 4 2
2 3
1 4
3 4
1 2
Sample Output 1
4 3 2 1
Sample Input 2
4 3 10062006
2 3
1 4
3 4
Sample Output 2
1 2 3 4
Notes
Ở test ví dụ thứ nhất:
Ngày đầu tiên:
Sau sự kiện ~1~, vị trí của các con bò là: ~1~ ~3~ ~2~ ~4~
Sau sự kiện ~2~: ~4~ ~2~ ~3~ ~1~
Sau sự kiện ~3~: ~4~ ~2~ ~1~ ~3~
Sau sự kiện ~4~: ~2~ ~4~ ~1~ ~3~
Ngày thứ hai:
Sau sự kiện ~1~: ~2~ ~1~ ~4~ ~3~
Sau sự kiện ~2~: ~3~ ~4~ ~1~ ~2~
Sau sự kiện ~3~: ~3~ ~4~ ~2~ ~1~
Sau sự kiện ~4~: ~4~ ~3~ ~2~ ~1~
Comments
This comment is hidden due to too much negative feedback. Show it anyway.