2318 . 煎鍋貼

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

97.1% (66/68)

Submission's AC Ratio

69.7% (76/109)

Tags

CKcon 2023-CKcon

Description

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

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

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

Input Format

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

對於所有測試資料：

  • 1≤N≤105
  • 1≤Ai≤Bi≤109

Output Format

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

  • 1≤K≤105
  • 1≤Tj≤109
  • 1≤Cj≤Dj≤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=A1≤1≤B1=2
1=A2≤1≤B2=1
2=A3≤3≤B3=3
4=A4≤4≤B4=4
1=A5≤1≤B5=1

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 N≤20 20
3 0~1, 10~19 Bi≤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
Submit
Back to Top