1010 . 外送系統優化

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc
有人要寫 p6 嗎 > <

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

ntucpc-speedrun2

Description

完整題本 PDF：中文、英文、馬來文。

你正在為一間提供無人機遞送服務的公司設計排程系統。每位顧客都有一組無人機起飛時間，表示無人機可以出發為他們遞送貨物的時間點。

為了提升無人機的整體調度效率，你需要找出一段時間區間 $[l, r]$，使得每位顧客至少有一個起飛時間落在此區間內。

請找出滿足此條件的最短區間 $[l, r]$。若有多個區間長度相同，請選擇 $l$ 最小的區間。

Input Format

第一行輸入一個整數 $k$，代表顧客的數量。
接下來 $k$ 行中的第 $i$ 行包含一個整數 $n_i$，代表第 $i$ 位顧客的起飛時間數量，後面跟著 $n_i$ 個相異整數，表示這些起飛時間。

  • $1 \leq k \leq 10 ^ 5$
  • $1 \leq n_i \leq 10 ^ 5$
  • $\sum_{i=1} ^ {k} n_i \leq 10 ^ 5$
  • 每個起飛時間都是不超過 $10 ^ 9$ 的正整數。

Output Format

請輸出兩個整數 $l$ 與 $r$，表示一個最短的時間區間 $[l, r]$，使得每位顧客至少有一個起飛時間位於該區間內。

Sample Input 1

3
5 4 10 24 26 15
4 4 9 12 20
5 5 22 30 18 9

Sample Output 1

4 5

Hints

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 2097152 65536
1 1000 2097152 65536
2 1000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
12 1000 2097152 65536
13 1000 2097152 65536
14 1000 2097152 65536
15 1000 2097152 65536
16 1000 2097152 65536
17 1000 2097152 65536
18 1000 2097152 65536
19 1000 2097152 65536
20 1000 2097152 65536
21 1000 2097152 65536
22 1000 2097152 65536
23 1000 2097152 65536
24 1000 2097152 65536
25 1000 2097152 65536
26 1000 2097152 65536
27 1000 2097152 65536
28 1000 2097152 65536
29 1000 2097152 65536
30 1000 2097152 65536
31 1000 2097152 65536
32 1000 2097152 65536
33 1000 2097152 65536
34 1000 2097152 65536
35 1000 2097152 65536
36 1000 2097152 65536
37 1000 2097152 65536
38 1000 2097152 65536
39 1000 2097152 65536
40 1000 2097152 65536
41 1000 2097152 65536
42 1000 2097152 65536
43 1000 2097152 65536
44 1000 2097152 65536
Submit
Back to Top