你是一名將領,正在攻打一座城,而你必須先攻打城牆,
城牆的樣子會長下方這樣,會有多道城牆重疊,
你想知道最厚的地方城牆厚度為多少,方便擬定策略。
城牆厚度計算方式如下,以上圖為例,
$0\sim3$ 的地方僅有厚度為 $1$ 的城牆,
$3\sim6$ 則有厚度為 $1$ 與厚度為 $2$ 的城牆重疊,因此 $3\sim6$ 的城牆厚度為 $1+2=3$ ,
$6\sim8$ 的地方僅有厚度為 $2$ 的城牆。
所以最厚的地方位於 $3\sim6$ 的位置,厚度為 $3$ 。
若有兩道城牆分別在 $0\sim3$ 及 $4\sim6$ ,則 $3\sim4$ 沒有城牆。
第一行有一個正整數 $N\ (N\leq10^ 6)$ ,代表有幾道城牆。
接下來有 $N$ 行,每行有三個非負整數 $l,r,w\ (0\leq l<r\leq 10^ 9, 0<w \leq 10^ 5)$ ,代表有一道城牆位於 $l$ 到 $r$ (包含 $l,r$ ),厚度為 $w$ 。
請輸出一個正整數,代表城牆最厚的地方厚度為多少。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~6 | $N\leq3\times10^ 3$ 且 $l,r\leq2\times10^ 4$ | 16 |
2 | 0~13 | $l,r\leq10^ 5$ | 29 |
3 | 0~6, 14~20 | $N\leq10^ 5$ | 20 |
4 | 0~27 | 無特別限制 | 35 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 2000 | 65536 | 65536 | |
1 | 2000 | 65536 | 65536 | |
2 | 2000 | 65536 | 65536 | |
3 | 2000 | 65536 | 65536 | |
4 | 2000 | 65536 | 65536 | |
5 | 2000 | 65536 | 65536 | |
6 | 2000 | 65536 | 65536 | |
7 | 2000 | 65536 | 65536 | |
8 | 2000 | 65536 | 65536 | |
9 | 2000 | 65536 | 65536 | |
10 | 2000 | 65536 | 65536 | |
11 | 2000 | 65536 | 65536 | |
12 | 2000 | 65536 | 65536 | |
13 | 2000 | 65536 | 65536 | |
14 | 2000 | 65536 | 65536 | |
15 | 2000 | 65536 | 65536 | |
16 | 2000 | 65536 | 65536 | |
17 | 2000 | 65536 | 65536 | |
18 | 2000 | 65536 | 65536 | |
19 | 2000 | 65536 | 65536 | |
20 | 2000 | 65536 | 65536 | |
21 | 2000 | 65536 | 65536 | |
22 | 2000 | 65536 | 65536 | |
23 | 2000 | 65536 | 65536 | |
24 | 2000 | 65536 | 65536 | |
25 | 2000 | 65536 | 65536 | |
26 | 2000 | 65536 | 65536 | |
27 | 2000 | 65536 | 65536 |