2064 . 排水系統管理

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

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

User's AC Ratio

63.6% (7/11)

Submission's AC Ratio

34.4% (11/32)

Tags

CKcon 2018-CKcon

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 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 $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 (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
Submit
Back to Top