Ô ăn quan
View as PDFTrò chơi Ô ăn quan với các hạt sỏi là một trò chơi truyền thống mà Tí rất thích nhưng chơi mãi đến một ngày Tí cũng thấy nhàm chán. Vì vậy, Tí muốn biến đổi trò chơi này cho thú vị hơn. Tí kẻ trên mặt sân N ô liên tiếp và đánh số thứ tự các ô từ một đến N, lúc đầu các ô đều trống. Mỗi lượt chơi, Tí đưa ra hai số nguyên X và Y, Tí sẽ đặt thêm vào các ô từ ô thứ X đến ô thứ Y mỗi ô một viên sỏi. Lúc Tèo xuất hiện thì Tí đã chơi được M lượt chơi. Tèo khá hứng thú với trò chơi này nên cũng kẻ N ô song song với N ô mà Tí đã kẻ, sau đó Tèo lần lượt bốc hết từng đống sỏi trong từng ô của Tí để đặt vào từng ô của mình (mỗi ô chỉ đặt một lần) sao cho trong N ô của Tèo kẻ không có ô nào đứng sau chứa ít viên sỏi hơn ô đứng trước. Bạn hãy cho biết ô chính giữa trong dãy N ô của Tèo có bao nhiêu viên sỏi?
Dữ liệu vào:
- Dòng đầu tiên chứa hai số nguyên N và M (N lẻ và 1 ≤ N ≤ ~10^6~, 1 ≤ M ≤ ~10^6~)
- M dòng tiếp theo, dòng thứ i chứa hai số nguyên Xi và ~Y_i~ (1 ≤ ~X_i~ ≤ ~Y_i~ ≤ N) mô tả lượt chơi thứ i.
Dữ liệu ra:
- Là số lượng viên sỏi ở ô chính giữa trong dãy N ô của Tèo.
Ví dụ:
INP
7 3
1 4
3 5
2 6
OUT
2
Giới hạn:
- Có 40% test N và M ≤ ~10^4~ tương ứng 40% số điểm;
Comments
iloveamelia><