#P2206. 音乐水栅
音乐水栅
音乐水栅(Musical Water-fence)
题目描述
有 块并排放置的长方体木块。每块木块的长度均为 ,第 块木块的宽度为 、高度为 。原资料称木块高度各不相同(但提供的样例中存在重复高度,见下方说明)。水栅的前后有玻璃挡住,水只会在木块排列的左右方向流动。
每块木块正上方都有一个水龙头。下图为原题中的水栅正视图:

图1:音乐水栅结构示意
- 当水落到尚未积水的木块上时,会分成体积相等的两部分,分别向左、向右流动。例如,水从第3块木块上方流下,分成两股,落入左右两侧的低洼处。

*图2:从第3块木块注水后的分流示意
- 水落到已有的积水上时会与水融合;积水可以填满木块之间的凹槽,并在水位足够高时漫过相邻木块继续流动。例如,在第2块木块上方注水,当积水达到相邻木块的高度后,会继续流向第4块木块所在的低洼处。

*图3:积水升高并继续向相邻低洼处流动的示意
- 水最终可能从整个水栅的左端或右端流出,流出的部分视为浪费。
现依次执行 个加水命令,第 个命令表示向第 块木块的水龙头注入体积为 的水。
请分别计算最终从水栅左端、右端流出而浪费的水的总体积。
输入格式
第一行包含两个整数 。
接下来 行,每行两个实数 ,依次表示第 块木块的宽度和高度。
接下来 行,每行一个整数 和一个数 ,分别表示加水的位置编号和水的体积。
输出格式
输出两行:
- 第一行:从左端流出的水的总体积。
- 第二行:从右端流出的水的总体积。
每行保留小数点后三位。
输入样例
6 2
1 5
1 3
1 4
2 2
1 6
1 4
5 7
3 6
输出样例
0.500
3.500
数据范围
原始资料给出的分档如下:
- 的数据:。
- 的数据:。
- 的数据:。
- 的数据:。
- 的数据:。
其中 是有效木块编号,宽度为正。