TWIST - Twist and whirl - want to cheat
English | Vietnamese |
Một tay lừa đảo có tiếng l*** đã sáng tạo ra một phương pháp để lừa bịp mọi người. Có N cái bát úp thành 1 hàng ngang trên bàn, và ở dưới mỗi cái bát đều có một quả bóng nhỏ. Các quả bóng này được đánh số từ 1 đến N từ trái sang phải. Một thao tác của l*** sẽ làm đảo ngược thứ tự của một dãy bát liên tiếp, ví dụ 2,3,4,5 thành 5,4,3,2. Sau khi l*** thực hiện M thao tác như vậy, bạn cần phải tìm ra số hiệu của N quả bóng nằm dưới N cái bát theo thứ tự từ trái sang phải.
Input
Dòng đầu chứa 2 số nguyên N và M (1<=N<=100000, 1<=M<=100000). Mỗi dòng trong M dòng tiếp theo chứa 2 số nguyên Pi, Qi (1<=Pi<=Qi<=N) - vị trí của cái bát trái nhất và phải nhất trong dãy bát liên tiếp bị đảo ngược.
Output
In ra N số nguyên trên 1 dòng thể hiện số hiệu của N quả bóng theo thứ tự từ trái sang phải.
Sample test(s)
Input
Test #1
5 2
1 3
4 5
Test #2
5 2
1 4
2 5
5 2
1 3
4 5
Test #2
5 2
1 4
2 5
Output
Test #1
3 2 1 5 4
Test #2 D
4 5 1 2 3
3 2 1 5 4
Test #2 D
4 5 1 2 3
Lưu ý: Thuật toán trâu bò sẽ bị TLE. Have fun! :D
Added by: | Race with time |
Date: | 2010-11-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | NEERC Southern Subregion 2003 - 2004 |