TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

36.8% (7/19)

Description

排水系統是都市中不可或缺的一環,設計良好的排水系統可以在強降雨的時候降低淹水的機率,就算淹水也可以用很快的時間把積水排掉。

我們使用一個非常簡單的模型來模擬排水系統的運作:假設整個城市是一個圓柱型的水桶,而排水系統相當於在水桶的側面有$N$個排水閘門。每個排水閘門只有開或關兩種選擇:打開時,若當時水位高於這個閘門的位置,則這個打開的水閘門會使水位每秒下降1單位;而若水位低於閘門的位置,那麼這個水閘門不會排出任何水。
注意水的流出是連續的,所以在某個水閘門打開時,若水位只高於該水閘門0.87秒,那這個水閘門會恰好使水位下降0.87單位。另外,每個水閘門的排水效果是疊加的,也就是若某個時刻有17個閘門正在作用(打開且水位高於它),則該時刻桶內的水位將以每秒17單位的速度下降。

現在排水系統的管理處想要演練當城市發生高度$H$單位的淹水時,要如何操作這$N$個閘門。為了演練方便,我們假設在發生淹水的時刻為0秒,而在排水的過程中不會有額外的降雨發生(也就是水位只會因閘門的排水而改變)。當然,閘門不是說開就開的,過快的排水可能會導致下游的淹水。因此,管理處擬定了一個閘門操作計畫,打算把第$i$個閘門在$l_i$秒時打開、在$r_i$秒時關閉。而有些閘門因為老舊的關係,在排完水之前是沒有辦法中途關閉的,這些閘門在計畫中會以$r_i=-1$表示。

你的任務就是幫管理處寫一個程式,輸入他們的閘門操作計畫,以及每個閘門的高度$d_i$,請你計算從開始到排完水(水位降至0時)需要經過多少秒。

Input Format

第一行有兩個整數$N, H$,分別代表總閘門數和起始的水位高度。
接著$N$行,每行都有三個整數$l_i, r_i, d_i$,分別代表一個閘門的開、關時間分別為$l_i,r_i$秒,以及該閘門的高度為$d_i$。若$r_i = -1$則代表這是個老舊、不能中途關閉的閘門。

對於所有測資,$N \leq 2 \times 10^ 5, H \leq 10^ 9, 0\leq d_i \leq H$,且若$r_i \neq -1$,則$0\leq l_i < r_i\leq P\leq 10^ 9$。

子任務(測資) 額外限制 分數
1 (0~24) $N \leq 20, H \leq 10^ 3, \epsilon = 10^ {-2},P \leq 10^ 3$ 11
2 (0~49) $H \leq 10^3, \epsilon = 10^ {-2}, P \leq 10^ 4$ 12
3 (50~59) $\epsilon = 10^ {-6}$,對於每個非負實數時間$t$,至多有一個閘門正在運作。 8
3 (60~74) $r_i = -1, \epsilon = 10^ {-6}$ 30
4 (0~99) $\epsilon = 10^ {-6}$ 39

Output Format

若水位永遠都沒辦法降至0,輸出-1
否則,輸出一個非負實數,代表水位降至0時總共經過了幾秒。
若你的答案和正確答案相對或絕對誤差其中一者不超過$\epsilon$(亦即$\frac{\lvert A - B\rvert}{\max(A, 1)} < \epsilon$,其中$A$是正確答案、$B$是你的答案),就會被視為正確。
(請注意每一個子任務測資的$\epsilon$不盡相同。)

Sample Input

Sample Input #1
1 10
1 -1 0

Sample Input #2
2 10
0 5 0
5 10 0

Sample Input #3
3 10
1 3 8
2 8 0
1 -1 1

Sample Input #4
5 10
0 -1 1
0 -1 2
0 -1 3
0 -1 4
0 -1 5

Sample Output

Sample Output #1
11.000000000

Sample Output #2
10.000000000

Sample Output #3
6.5000000000

Sample Output #4
-1

Hints

Problem Source

Problem set by edisonhello / waynetuinfor
Description by Yihda Yol
建國中學107學年度校隊選拔:初試pD

Subtasks

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