2200 . 導火面板改（Fire）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

24.0% (18/75)

Tags

Description

又是某天，蝸牛老師買了一塊大小為 $R\times C$ 的導火面板，將它鋪平並放在一間很大的教室中。而得知這件消息的搗蛋鬼小寧再次決定將這塊導火面板燒掉。

小寧的野心再次傳進了蝸牛老師耳中，他得知小寧打算設置 $N$ 個起火點，第 $i$ 個起火點將會在時間 $t_i$ 被設置在導火面板中 $(x_i,y_i)$ 的位置（導火面板的左上角是 $(0,0)$、最右下角是 $(R,C)$）。當起火點被設置的瞬間便會馬上開始燃燒並燃燒殆盡，且接下來會持續以 $1$ 格的秒速向上下左右四個方向燃燒。也就是說，對於任何一個介於 $(0,0)\sim (R,C)$ 的實數點 $(x,y)$，只要時間 $t$ 存在一個起火點 $i$ 滿足 $|x_i-x|+|y_i-y|\le t-t_i$，點 $(x,y)$ 就會被視為燃燒殆盡。

不幸的是，蝸牛老師手邊有工作無法離身，不過他想知道這條導火面板要多久才會被燃燒殆盡，因為小寧肯定會等到導火面板燒完後才離開現場，這樣蝸牛老師就可以分配時間過去抓他。你可以告訴蝸牛老師在何時導火面板才會被燃燒殆盡嗎？注意到，因為蝸牛老師覺得小數點很煩，所以請你找出最早在哪個面板才會被燃燒殆盡。

註：若某個起火點要設置的當下，該位置已被燃燒完畢，則小寧會跳過這次的設置。
註2：若 $R=0$ 或 $C=0$，你可以把導火面板當作一條導火線；若 $R=C=0$，你可以把導火面板當作一個火種，即第一次點燃的瞬間整塊面板便瞬間被燃燒殆盡。

Input Format

首行有三個正整數 $N,R,C$，代表起火點的個數和導火面板的大小。
接下來 $N$ 行，第 $i$ 行三個整數 $t_i,x_i,y_i$，代表第 $i$ 個起火點的將會在時間 $t_i$ 被設置在導火面板中 $(x_i,y_i)$ 的位置。
所有數字皆以單一空格隔開。

Output Format

輸出幾個整數秒後面板會被燃燒殆盡。

Sample Input 1

1 3 4
3 2 2

Sample Output 1

7

Sample Input 2

2 0 9
1 0 1
1 0 9

Sample Output 2

5

Sample Input 3

3 5 8
1 0 3
4 3 7
2 4 2

Sample Output 3

7

Hints

測資限制：

  • $1\le N\le 5\times 10 ^ 4$。
  • $0\le R,C\le 10^ 9$。
  • $1\le t_i\le 10^ 9$。
  • $0\le x_i\le R$。
  • $0\le y_i\le C$。

本題共有 $4$ 組測試題組，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

  1. ($26\%$) $R=0$。
  2. ($21\%$) $R,C\le 2000$。
  3. ($37\%$) $R,C\le 10^ 5$。
  4. ($16\%$) 無額外限制。

Problem Source

2021 板中TOI模考模擬賽

Subtasks

No. Testdata Range Constraints Score
1 3~23 $R=0$。 26
2 24~52 $R,C\le 2000$。 21
3 24~73 $R,C\le 10^ 5$。 37
4 0~94 無額外限制。 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 4
1 5000 524288 65536 4
2 5000 524288 65536 4
3 5000 524288 65536 1 4
4 5000 524288 65536 1 4
5 5000 524288 65536 1 4
6 5000 524288 65536 1 4
7 5000 524288 65536 1 4
8 5000 524288 65536 1 4
9 5000 524288 65536 1 4
10 5000 524288 65536 1 4
11 5000 524288 65536 1 4
12 5000 524288 65536 1 4
13 5000 524288 65536 1 4
14 5000 524288 65536 1 4
15 5000 524288 65536 1 4
16 5000 524288 65536 1 4
17 5000 524288 65536 1 4
18 5000 524288 65536 1 4
19 5000 524288 65536 1 4
20 5000 524288 65536 1 4
21 5000 524288 65536 1 4
22 5000 524288 65536 1 4
23 5000 524288 65536 1 4
24 5000 524288 65536 2 3 4
25 5000 524288 65536 2 3 4
26 5000 524288 65536 2 3 4
27 5000 524288 65536 2 3 4
28 5000 524288 65536 2 3 4
29 5000 524288 65536 2 3 4
30 5000 524288 65536 2 3 4
31 5000 524288 65536 2 3 4
32 5000 524288 65536 2 3 4
33 5000 524288 65536 2 3 4
34 5000 524288 65536 2 3 4
35 5000 524288 65536 2 3 4
36 5000 524288 65536 2 3 4
37 5000 524288 65536 2 3 4
38 5000 524288 65536 2 3 4
39 5000 524288 65536 2 3 4
40 5000 524288 65536 2 3 4
41 5000 524288 65536 2 3 4
42 5000 524288 65536 2 3 4
43 5000 524288 65536 2 3 4
44 5000 524288 65536 2 3 4
45 5000 524288 65536 2 3 4
46 5000 524288 65536 2 3 4
47 5000 524288 65536 2 3 4
48 5000 524288 65536 2 3 4
49 5000 524288 65536 2 3 4
50 5000 524288 65536 2 3 4
51 5000 524288 65536 2 3 4
52 5000 524288 65536 2 3 4
53 5000 524288 65536 3 4
54 5000 524288 65536 3 4
55 5000 524288 65536 3 4
56 5000 524288 65536 3 4
57 5000 524288 65536 3 4
58 5000 524288 65536 3 4
59 5000 524288 65536 3 4
60 5000 524288 65536 3 4
61 5000 524288 65536 3 4
62 5000 524288 65536 3 4
63 5000 524288 65536 3 4
64 5000 524288 65536 3 4
65 5000 524288 65536 3 4
66 5000 524288 65536 3 4
67 5000 524288 65536 3 4
68 5000 524288 65536 3 4
69 5000 524288 65536 3 4
70 5000 524288 65536 3 4
71 5000 524288 65536 3 4
72 5000 524288 65536 3 4
73 5000 524288 65536 3 4
74 5000 524288 65536 4
75 5000 524288 65536 4
76 5000 524288 65536 4
77 5000 524288 65536 4
78 5000 524288 65536 4
79 5000 524288 65536 4
80 5000 524288 65536 4
81 5000 524288 65536 4
82 5000 524288 65536 4
83 5000 524288 65536 4
84 5000 524288 65536 4
85 5000 524288 65536 4
86 5000 524288 65536 4
87 5000 524288 65536 4
88 5000 524288 65536 4
89 5000 524288 65536 4
90 5000 524288 65536 4
91 5000 524288 65536 4
92 5000 524288 65536 4
93 5000 524288 65536 4
94 5000 524288 65536 4
Submit
Back to Top