TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

87.5% (98/112)

Submission's AC Ratio

23.9% (176/736)

Description

小智的學校在天空之城,父母親每天開直升機送他上下學,上學途中小智可以一邊抓寶。請寫個程式幫助小智的父母親規劃一條路徑以便在從家裡到學校的路上,小智可以抓到最多的寶貝。

學校與小智家之間所有的位置均等劃分成 $N \times N$ 的格子(如下所示),每個格子以座標 $(x, y)$ 表示,其中 $x$ 代表水平距離,$y$ 代表高度,若小智家的座標設為原點 $(0, 0)$,學校的座標則為 $(N-1, N-1)$。 直升機飛行的路線被設定成每次只能向右或向上推進一格,也就是說,若直升機在 $(x, y)$ 上,下一步只能飛達 $(x+1, y)$ 或 $(x, y+1)$,當然,直升機也不可以飛超過 $0 \le x<N$ 及 $0 \le y < N$ 的範圍。

小智上學的路途上一共有 $N$ 隻寶貝,每隻寶貝可以被補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說,對於寶貝 $P(i), 0 \le i < N$,要捕抓到 $P(i)$,小智必須經過下列座標之一:$\{(x, y)| S(i)\leq x\leq T(i), y=i\}$,其中 $0 \le S(i), T(i) <N$。

上圖是一個N=5 的例子,藍色區塊顯示可以捕抓到寶貝的座標位置,例如寶貝0 (P(0))的捕獲區域為 S(0)≦x≦T(0) (而S(0)=1, T(0)=2),且y = 0。每一個寶貝可捕獲區域都一定在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的飛行路徑,因為每一步都只有向右或向上,沿這一條路徑共可以捕抓到四隻寶貝,即P(0), P(1), P(2), P(4),也是所有可能路徑中可以捕抓到寶貝數最多的。

Input Format

輸入的第一行是座標範圍 $N$,接下來的 $N$ 行,每一行有兩個以空白隔開的整數$S(i)$ 與 $T(i)$,依序是 $i = 0, 1, \cdots , N-1$,其中 $0 \le S(i) \le T(i) < N$。

Output Format

輸出一整數為小智最多可以抓到的寶貝數量。

Sample Input

輸入範例一 (符合子題一、三)
5
2 2
1 1
0 0
2 2
4 4
輸入範例二 (符合子題二、四、五)
5
1 3
0 1
3 4
0 0
2 3

Sample Output

輸出範例一
3

輸出範例二
4

Hints

Problem Source

105學年度高級中學資訊學科能力競賽決賽 程式設計試題第四題
2021.03.23 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Constraints Score
1 0~8 $N \le 10$,且對所有 $i$,$S(i)=T(i)$ 17
2 0~16 $N \le 5000$ 13
3 17~23 $N \le 100000$,且對所有 $i$,$S(i)=T(i)$ 13
4 0~35 $N \le 300000$ 25
5 0~51 $N \le 800000$ 32

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 262144 1 2 4 5
1 1000 524288 262144 1 2 4 5
2 1000 524288 262144 1 2 4 5
3 1000 524288 262144 1 2 4 5
4 1000 524288 262144 1 2 4 5
5 1000 524288 262144 1 2 4 5
6 1000 524288 262144 1 2 4 5
7 1000 524288 262144 1 2 4 5
8 1000 524288 262144 1 2 4 5
9 1000 524288 262144 2 4 5
10 1000 524288 262144 2 4 5
11 1000 524288 262144 2 4 5
12 1000 524288 262144 2 4 5
13 1000 524288 262144 2 4 5
14 1000 524288 262144 2 4 5
15 1000 524288 262144 2 4 5
16 1000 524288 262144 2 4 5
17 1000 524288 262144 3 4 5
18 1000 524288 262144 3 4 5
19 1000 524288 262144 3 4 5
20 1000 524288 262144 3 4 5
21 1000 524288 262144 3 4 5
22 1000 524288 262144 3 4 5
23 1000 524288 262144 3 4 5
24 1000 524288 262144 4 5
25 1000 524288 262144 4 5
26 1000 524288 262144 4 5
27 1000 524288 262144 4 5
28 1000 524288 262144 4 5
29 1000 524288 262144 4 5
30 1000 524288 262144 4 5
31 1000 524288 262144 4 5
32 1000 524288 262144 4 5
33 1000 524288 262144 4 5
34 1000 524288 262144 4 5
35 1000 524288 262144 4 5
36 1000 524288 262144 5
37 1000 524288 262144 5
38 1000 524288 262144 5
39 1000 524288 262144 5
40 1000 524288 262144 5
41 1000 524288 262144 5
42 1000 524288 262144 5
43 1000 524288 262144 5
44 1000 524288 262144 5
45 1000 524288 262144 5
46 1000 524288 262144 5
47 1000 524288 262144 5
48 1000 524288 262144 5
49 1000 524288 262144 5
50 1000 524288 262144 5
51 1000 524288 262144 5