#P2206. 音乐水栅

音乐水栅

音乐水栅(Musical Water-fence)

题目描述

有 NN 块并排放置的长方体木块。每块木块的长度均为 11,第 ii 块木块的宽度为 LiL_i、高度为 HiH_i。原资料称木块高度各不相同(但提供的样例中存在重复高度,见下方说明)。水栅的前后有玻璃挡住,水只会在木块排列的左右方向流动。

每块木块正上方都有一个水龙头。下图为原题中的水栅正视图:

图1:音乐水栅结构示意

  • 当水落到尚未积水的木块上时,会分成体积相等的两部分,分别向左、向右流动。例如,水从第3块木块上方流下,分成两股,落入左右两侧的低洼处。

*图2:从第3块木块注水后的分流示意

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

*图3:积水升高并继续向相邻低洼处流动的示意

  • 水最终可能从整个水栅的左端或右端流出,流出的部分视为浪费。

现依次执行 MM 个加水命令,第 jj 个命令表示向第 WjW_j 块木块的水龙头注入体积为 VjV_j 的水。

请分别计算最终从水栅左端、右端流出而浪费的水的总体积。

输入格式

第一行包含两个整数 N,MN,M。

接下来 NN 行,每行两个实数 Li,HiL_i,H_i,依次表示第 ii 块木块的宽度和高度。

接下来 MM 行,每行一个整数 WjW_j 和一个数 VjV_j,分别表示加水的位置编号和水的体积。

输出格式

输出两行:

  • 第一行:从左端流出的水的总体积。
  • 第二行:从右端流出的水的总体积。

每行保留小数点后三位。

输入样例

6 2
1 5
1 3
1 4
2 2
1 6
1 4
5 7
3 6

输出样例

0.500
3.500

数据范围

原始资料给出的分档如下:

  • 50%50\% 的数据:N,M≤100N,M\le 100。
  • 70%70\% 的数据:N,M≤1000N,M\le 1000。
  • 80%80\% 的数据:N,M≤10000N,M\le 10000。
  • 90%90\% 的数据:N,M≤100000N,M\le 100000。
  • 100%100\% 的数据:N,M≤1000000N,M\le 1000000。

其中 WjW_j 是有效木块编号,宽度为正。