TWIST - Twist and whirl - want to cheat

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/twist


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

Output
Test #1
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


Được gửi lên bởi:Race with time
Ngày:2010-11-04
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:NEERC Southern Subregion 2003 - 2004

hide comments
2015-09-04 17:27:15 [Nghien] Le Long
splay tree rồi
2010-11-06 03:42:23 Race with time
Cam on thay a. Dung la co mot so test bi sai (Qi > n).
Bo test da duoc sua lai.
2010-11-05 11:35:28 Lê Minh Hoàng
Trong các test cases có trường hợp Qi > n.
Số n trong input bị sai?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.