2289 . 昨天晚上，一等一被殺了

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

97.3% (36/37)

Submission's AC Ratio

57.0% (45/79)

Tags

CKsim 2022-CKsim

Description

一年一度的 NHSPC (National High School Playing Contest) 又要到了！今年最受到矚目的競賽項目就是狼人殺了。這裡的狼人殺與一般的不一樣，最大的不同就是他有一個叫做區間查殺的規定。

具體來講，一開始每個人會排成一列，編號 $1$ 至 $n$，狼人每次殺人都會選定一段區間 $[l,r]$，若$[l,r]$中還沒有人出局，狼人就會使 $[l,r]$ 裡面至少有一個人出局。

遊戲總共進行了 $q$ 回合，現在給你這 $q$ 回合內狼人選擇的 $[l,r]$，請求出至少有多少人出局了。

Input Format

第一行會有兩個整數 $n$, $q$，分別表示人數以及遊戲進行的回合數
接下來會有 $q$ 行，每行是兩個整數 $a_i, \ b_i$，分別代表第 i 回合選擇了 $a_i, \ b_i$ 這段區間。

對於所有測試資料，滿足 $n \leq 200000$, $q \leq 500000$, $1 \leq a_i \leq b_i \leq n$。

Output Format

輸出一個整數，代表最少有多少人出局了。

Sample Input 1

Sample Input 1:
5 3
1 2
2 3
4 5

Sample Input 2:
6 7
1 5
3 6
5 6
2 3
1 3
4 5
1 1

Sample Output 1

Sample Output 1:
2

Sample Output 2:
3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~11 $n \leq 20, q \leq 20$ 27
3 0~21 $n \leq 5000, q \leq 5000$ 33
4 0~31 無其他限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3 4
1 1000 65536 65536 1 2 3 4
2 1000 65536 65536 2 3 4
3 1000 65536 65536 2 3 4
4 1000 65536 65536 2 3 4
5 1000 65536 65536 2 3 4
6 1000 65536 65536 2 3 4
7 1000 65536 65536 2 3 4
8 1000 65536 65536 2 3 4
9 1000 65536 65536 2 3 4
10 1000 65536 65536 2 3 4
11 1000 65536 65536 2 3 4
12 1000 65536 65536 3 4
13 1000 65536 65536 3 4
14 1000 65536 65536 3 4
15 1000 65536 65536 3 4
16 1000 65536 65536 3 4
17 1000 65536 65536 3 4
18 1000 65536 65536 3 4
19 1000 65536 65536 3 4
20 1000 65536 65536 3 4
21 1000 65536 65536 3 4
22 1000 65536 65536 4
23 1000 65536 65536 4
24 1000 65536 65536 4
25 1000 65536 65536 4
26 1000 65536 65536 4
27 1000 65536 65536 4
28 1000 65536 65536 4
29 1000 65536 65536 4
30 1000 65536 65536 4
31 1000 65536 65536 4
Submit
Back to Top