User's AC Ratio in this contest

14.3% (4/28)

Submission's AC Ratio in this contest

4.4% (4/91)

Description

你是一名將領，正在攻打一座城，而你必須先攻打城牆，
城牆的樣子會長下方這樣，會有多道城牆重疊，
你想知道最厚的地方城牆厚度為多少，方便擬定策略。

城牆厚度計算方式如下，以上圖為例，
$0\sim3$ 的地方僅有厚度為 $1$ 的城牆，
$3\sim6$ 則有厚度為 $1$ 與厚度為 $2$ 的城牆重疊，因此 $3\sim6$ 的城牆厚度為 $1+2=3$ ，
$6\sim8$ 的地方僅有厚度為 $2$ 的城牆。
所以最厚的地方位於 $3\sim6$ 的位置，厚度為 $3$ 。

若有兩道城牆分別在 $0\sim3$ 及 $4\sim6$ ，則 $3\sim4$ 沒有城牆。

Input Format

第一行有一個正整數 $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$ 。

Output Format

請輸出一個正整數，代表城牆最厚的地方厚度為多少。

Sample Input 1

2
0 6 1
3 8 2

Sample Output 1

Sample Input 2

3
0 5 3
2 9 2
6 13 3

Sample Output 2

Sample Input 3

3
0 5 3
2 10 2
6 13 3

Sample Output 3

Sample Input 4

3
0 5 1
3 7 1
5 10 1

Sample Output 4

Hints

Problem Source

Subtasks

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

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	2000	65536	65536	1 2 3 4
1	2000	65536	65536	1 2 3 4
2	2000	65536	65536	1 2 3 4
3	2000	65536	65536	1 2 3 4
4	2000	65536	65536	1 2 3 4
5	2000	65536	65536	1 2 3 4
6	2000	65536	65536	1 2 3 4
7	2000	65536	65536	2 4
8	2000	65536	65536	2 4
9	2000	65536	65536	2 4
10	2000	65536	65536	2 4
11	2000	65536	65536	2 4
12	2000	65536	65536	2 4
13	2000	65536	65536	2 4
14	2000	65536	65536	3 4
15	2000	65536	65536	3 4
16	2000	65536	65536	3 4
17	2000	65536	65536	3 4
18	2000	65536	65536	3 4
19	2000	65536	65536	3 4
20	2000	65536	65536	3 4
21	2000	65536	65536	4
22	2000	65536	65536	4
23	2000	65536	65536	4
24	2000	65536	65536	4
25	2000	65536	65536	4
26	2000	65536	65536	4
27	2000	65536	65536	4

Submit

Status

Ranklist

42 . 攻城行動