Bedao Mini Contest 24 - Reverse Cow

View as PDF

Submit solution


Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Please read the guidelines before commenting.



  • -21
    chunguyen2k8  commented on May 3, 2024, 6:40 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.