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