TopCoder

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

User's AC Ratio

96.4% (53/55)

Submission's AC Ratio

70.5% (62/88)

Tags

Description

水果王國舉行了包鍋貼大賽!經過一番廝殺,參賽者總共包好了 $N$ 個鍋貼,並且按照編號 $1 \sim N$ 排成了一排,但是直到結束他們才想到,要評分之前還要先把鍋貼煎好。
為了解決這個問題,他們準備了一些鍋子來煎,他們做了如下的要求:

  • 每個鍋貼都要裝在其中一個鍋子裡
  • 同一個鍋子的起鍋時間要一樣
  • 鍋子必須裝著編號連續的鍋貼,例如,不能有一個鍋子恰裝著編號為 $1, 3, 4$ 的鍋貼

但是不同的鍋貼是有不同的烹調方式的,具體來說,對於編號為 $i$ 的鍋貼,他的起鍋時間必須介在 $[A_i,B_i]$ 之間才能保證美味。
鍋子很大,但是搬運鍋子很費工,所以他們希望能用最少的鍋子把所有鍋貼煎好。
現在這個問題交給了你,請你設計出一種放鍋貼的方式使用最少的鍋子。

Input Format

第一行會有一個整數 $N$,代表有幾個鍋貼,接下來的 $N$ 行,每行會有兩個整數 $A_i, B_i$,代表第 $i$ 個鍋貼的起鍋時間需要界在 $[A_i, B_i]$ 之間

對於所有測試資料:

  • $1 \leq N \leq 10^ 5$
  • $1 \leq A_i \leq B_i \leq 10^ 9$

Output Format

第一行請輸出一個整數 $K$,代表總共進行了幾次操作。
接下來請輸出 $K$ 行,每行包含 $3$ 個整數 $T_j, C_j, D_j$,代表第 $ j$ 個鍋子會在時間點 $T_j$ 起鍋, 並且上面有第 $[C_j, D_j]$ 個鍋貼

  • $1 \leq K \leq 10^ 5$
  • $1 \leq T_j \leq 10^ 9$
  • $1 \leq C_j \leq D_j \leq N$

Sample Input 1

5
1 2
1 1
2 3
4 4
1 1

Sample Output 1

4
4 4 4
1 5 5
3 3 3
1 1 2

Sample Input 2

6
4 7
3 8
9 10
5 13
8 9
10 18

Sample Output 2

3
5 1 2
9 3 5
10 6 6

Hints

對於範測一,分配的結果如下,
第一個鍋子裝著第四個鍋貼,並且在時間 4 起鍋。
第二個鍋子裝著第五個鍋貼,並且在時間 1 起鍋。
第三個鍋子裝著第三個鍋貼,並且在時間 3 起鍋。
第四個鍋子裝著第一個和第二個鍋貼,並且在時間 1 起鍋。
可以看出這樣的分配滿足要求,因為
$1 = A_1 \leq 1 \leq B_1 = 2$
$1 = A_2 \leq 1 \leq B_2 = 1$
$2 = A_3 \leq 3 \leq B_3 = 3$
$4 = A_4 \leq 4 \leq B_4 = 4$
$1 = A_5 \leq 1 \leq B_5 = 1$

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 $N \leq 20$ 20
3 0~1, 10~19 $B_i \leq 100$ 37
4 0~29 無其他限制 43

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2 3 4
1 1000 131072 65536 1 2 3 4
2 1000 131072 65536 2 4
3 1000 131072 65536 2 4
4 1000 131072 65536 2 4
5 1000 131072 65536 2 4
6 1000 131072 65536 2 4
7 1000 131072 65536 2 4
8 1000 131072 65536 2 4
9 1000 131072 65536 2 4
10 1000 131072 65536 3 4
11 1000 131072 65536 3 4
12 1000 131072 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 4
21 1000 65536 65536 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