TopCoder

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

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

33.3% (7/21)

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$。

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

No. Testdata Range Constraints Score
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
4 60~74 $r_i = -1, \epsilon = 10^ {-6}$ 30
5 0~99 $\epsilon = 10^ {-6}$ 39

Testdata and Limits

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