水题

发布时间: 2017年6月19日 00:24   时间限制: 5000ms   内存限制: 128M

在地上按顺序摆放着  n 个水桶。编号依次为 1,2,3,...,n 。每个水桶有一定的容量,可以容纳不同体积的水。不幸的是,每个桶都是破的,每秒都会漏掉一定数量的水。

i 个桶初始有 x_i  毫升的水,每秒钟会漏掉 y_i 毫升的水,容量为 z_i 毫升。也就是第 i 个桶最多装 z_i  毫升的水,每过1秒,就会漏掉 y_i  毫升的水,当然桶中没有水时,是不会漏出水的。

现在有一个加水的机器。这个机器可以给连续区间 [L, R]  内的水桶加满水。加水不需要时间,瞬间完成。每次加水时,这个机器加的水的总量取决于选择的区间,以及这个区间里面的水桶当前时刻拥有的水量。

现在我们面临一个很简单的问题。我们给出了每个桶的 x_i, y_i, z_i ,以及这个机器进行 m  次加水的时刻以及选择的区间,请求出在 m  次加水操作中,加水机器加水量的总和。

第一行含有一个正整数 T,表示有 T 组测试数据。
每组数据第一行是一个正整数 n,表示有 n 个水桶。
接下来 n 行,每行三个整数 x_i,y_i,z_i。
接下来一个正整数 m,表示有 m 次加水。
接下来的 m 行,描述的是每次加水的信息,包含三个整数 t_i,L_i,R_i,保证加水的时刻是严格递增给出的。同一时刻不会有两次的加水操作。
当前时刻是0,时刻0水桶中的水量就是初始值。加水是瞬间完成的,不计算时间。漏水是在两个时刻之间的,不会和加水冲突。
约定
    T≤20;
    n≤10^5;
    0≤x_i,y_i,z_i≤10^6;
    x_i≤z_i;
    0<m≤10^5;
    0<t_i≤2×10^5;
    1≤L_i≤R_i≤n。

对于每组测试用例,输出:
第一行:Case #: (# 要替换成对应的数字)。
第二行输出一个整数,表示加水机器总共的加水量。

复制
1
4
2 1 4
3 2 5
8 1 10
0 3 2
3
1 1 4
4 2 3
9 1 4
Case 1:
36

样例中有4个水桶。
在0时刻,水量分别为2 3 8 0;
在1时刻,水量分别为1 1 7 0,这个时候机器加水,加水3 + 4 + 3 + 2 = 12。水量变成了4 5 10 2;
在2时刻,水量分别为3 3 9 0;
在3时刻,水量分别为2 1 8 0;
在4时刻,水量分别为1 0 7 0,这个时候机器加水,加水5 + 3 = 8,水量变为1 5 10 2;
到时刻9的时候,水量分别为0 0 5 0,这个时候加水,加水4 + 5 + 5 + 2 = 16,水量变为4 5 10 2。
因此总共的水量为12 + 8 + 16 = 36。

1772

old_judge

old_judge_None