| 题目名称 | 940. [HAOI 2012]矩形覆盖a |
|---|---|
| 输入输出 | jxfgx.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2012-07-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：10， 通过率：20% | ||||
 FoolMike |
100 | 8.275 s | 78.26 MiB | C++ |
 梦那边的美好ET |
100 | 8.403 s | 78.26 MiB | C++ |
 201101 |
70 | 2.352 s | 3.16 MiB | C++ |
 Makazeu |
70 | 2.887 s | 0.32 MiB | C++ |
 fjzzq2002 |
40 | 3.497 s | 102.40 MiB | C++ |
|
Makazeu |
40 | 3.727 s | 0.32 MiB | C++ |
 zbtrs |
40 | 6.030 s | 91.80 MiB | C++ |
|
zbtrs |
40 | 6.076 s | 80.33 MiB | C++ |
|
fjzzq2002 |
0 | 0.000 s | 0.00 MiB | C++ |
|
fjzzq2002 |
0 | 0.284 s | 102.40 MiB | C++ |
| 本题关联比赛 | |||
| 20120721 | |||
| 关于 矩形覆盖a 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
O(nk)的四分树已被常数卡掉，坐等会正解神犇切题，一定要发题解啊！
| ||||
【题目描述】
有一个N*M的白色矩形。有两种操作。
1. 用一块黑布盖住矩形的一部分
2. 把之前放入的某块黑布拿走
对于每次操作，输出当前矩形上黑布的面积
【输入格式】
第一行三个整数N，M，K表示矩形的面积N*M和操作次数K
之后K行，每行五个整数a，X1，Y1，X2，Y2
a表示操作类型，1表示放入黑布，2表示拿走黑布
X1，Y1，X2，Y2表示黑布的左上角坐标和右下角坐标
【输出格式】
共K行，第i行表示第i次操作后矩形上黑布的面积
【输入样例】
3 4 4
1 1 2 2 4
1 2 2 3 3
2 1 2 2 4
1 2 1 3 4
【输出样例】
6
8
4
8
【数据规模】
对于40%的数据 1<=N,M<=100 , 1<=K<=100
对于70%的数据 1<=N<=2000 , 1<=M<=100 , 1<=K<=50000
对于100%的数据 1<=N,M<=2000 , 1<=K<=50000
1<=X1<=X2<=N , 1<=Y1<=Y2<=M