途灵编程 首页 题库 课程 竞赛 评测 题库(选择) 测试(选择) 帮助 返回比赛
登录

B. baobao

内存限制：256 MiB 时间限制：1000 ms 输入文件: baobao.in 输出文件: baobao.out
题目类型：传统 评测方式：文本比较
转到题库 提交记录 返回比赛

题目描述

小 R 是一个可爱的女孩子，她希望跟大家抱抱，顺便给大家分蛋糕吃。

蛋糕是一个大小为 a\times b\times c 的长方体，其中每个单位正方体都被赋予了一个坐标 (x,y,z) （ 1\le x\le a,1\le y\le b,1\le z\le c ）。

共进行 m 次切蛋糕操作，每次按如下三种方式之一切分：

  1. 切出 x\le k 的部分分给大家。
  2. 切出 y\le k 的部分分给大家。
  3. 切出 z\le k 的部分分给大家。

由于她自己也想吃蛋糕，她希望知道在每次切蛋糕后，还剩下多少体积没有分给大家。

输入格式

第一行四个整数 a,b,c,m ，表示蛋糕的大小和切蛋糕次数。

接下来 m 行，每行两个整数 op,k ，表示进行【题目描述】中的第 op 种操作，参数为 k 。

输出格式

m 行，每行一个整数，表示剩余部分体积。

样例

样例输入 #1

3 3 3 2
1 2
2 1

样例输出 #1

9
6

样例 1 解释

第一次切蛋糕，将所有 x\le 2 的部分切掉，剩余的单位正方体有 (3,1,1),(3,1,2),(3,1,3),(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3) 共 9 个。

第二次切蛋糕，将所有 y\le 1 的部分切掉，剩余的单位正方体有 (3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3) 共 6 个。

样例输入 #2

1000000 1000000 1000000 6
1 123456
2 654321
3 233333
2 111111
1 333333
3 1000000

样例输出 #2

876544000000000000
303002853376000000
232302288589217792
232302288589217792
176680542935560631
0

样例 2 解释

第四次切蛋糕没有任何作用，因为第二次切蛋糕时 y\le 654321 的部分已经被切掉，此时已经不存在 y\le 111111 的单位正方体。

注意每次操作中的参数 k 是初始时决定的绝对坐标，不会随着操作的进行而改变。

数据范围与提示

本题共 20 个测试点，每个测试点 5 分。

对于全部数据，保证 1\le a,b,c\le 10^6 ， 1\le m\le 2\times 10^5 ， op\in\{1,2,3\} ，若 op=1 则 1\le k\le a ，若 op=2 则 1\le k\le b ，若 op=3 则 1\le k\le c 。

  • 对于测试点 1\sim 5 ：保证 a,b,c,m\le 100 。
  • 对于测试点 6\sim 10 ：保证 b=c=1 ， op=1 。
  • 对于测试点 11\sim 15 ：保证 c=1 ， op\in\{1,2\} 。
  • 对于测试点 16\sim 20 ：无特殊限制。

注意

采用文件输入输出模式，输入文件名为：baobao.in， 输出文件名为：baobao.out.

途灵编程