TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

66.7% (8/12)

Submission's AC Ratio

36.4% (12/33)

Tags

Description

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

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

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

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

Input Format

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

對於所有測資,N2×105,H109,0diH,且若ri1,則0li<riP109

Output Format

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

Sample Input 1

1 10
1 -1 0

Sample Output 1

11.000000000

Sample Input 2

2 10
0 5 0
5 10 0

Sample Output 2

10.000000000

Sample Input 3

3 10
1 3 8
2 8 0
1 -1 1

Sample Output 3

6.5000000000

Sample Input 4

5 10
0 -1 1
0 -1 2
0 -1 3
0 -1 4
0 -1 5

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 N20,H103,ϵ=102,P103 11
2 0~49 H103,ϵ=102,P104 12
3 50~59 ϵ=106,對於每個非負實數時間t,至多有一個閘門正在運作。 8
4 60~74 ri=1,ϵ=106 30
5 0~99 ϵ=106 39

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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