这题用线段树就MLE。思路是逆向思维,然后每染色一段就利用并查集将该段移除,均摊复杂度为O(n*m)。

 /* 4056 */
#include <iostream>
#include <sstream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int id;
int xc, yc, w, h, c;
} draw_t; const int maxm = ;
const int maxn = ;
int fa[maxn][maxm];
draw_t draw[maxm];
int C[];
int n, m, q;
int xc, yc, w, h, c; int find(int rn, int x) {
if (fa[rn][x] == x)
return x;
return fa[rn][x] = find(rn, fa[rn][x]);
} void init() {
memset(C, , sizeof(C));
rep(i, , n)
rep(j, , m+)
fa[i][j] = j;
--n;
--m;
} int move(int xth, int l, int r) {
int ret = ; l = find(xth, l);
while (l <= r) {
++ret;
fa[xth][l] = l + ;
l = find(xth, l+);
} return ret;
} void DrawDiamond() {
int ly = yc - w;
int ry = yc + w;
int l, r, xth; xth = xc;
while (xth>= && ly<=ry) {
l = max(, ly);
r = min(m, ry);
C[c] += move(xth, l, r);
--xth;
++ly;
--ry;
} xth = xc + ;
ly = yc - w + ;
ry = yc + w - ;
while (xth<=n && ly<=ry) {
l = max(, ly);
r = min(m, ry);
C[c] += move(xth, l, r);
++xth;
++ly;
--ry;
}
} void DrawRectangle() {
int xth = xc;
int n_ = min(n, xc+h-);
int l = yc;
int r = min(m, yc+w-); while (xth <= n_) {
C[c] += move(xth, l, r);
++xth;
}
} void DrawTriangle() {
int w_ = w >> ;
int n_ = min(n, xc+w_);
int ly = yc - w_;
int ry = yc + w_;
int l, r;
int xth = xc; while (xth<=n_ && ly<=ry) {
l = max(, ly);
r = min(m, ry);
C[c] += move(xth, l, r);
++ly;
--ry;
++xth;
}
} void DrawCircle() {
int ly = yc - w;
int ry = yc + w;
int l, r;
__int64 w2 = 1LL * w * w, tmp;
int delta;
int xth = xc; l = max(, ly);
r = min(m, ry);
C[c] += move(xth, l, r); rep(i, , w+) {
tmp = 1LL * i * i;
delta = sqrt(w2 - tmp + 0.5);
ly = yc - delta;
ry = yc + delta;
l = max(, ly);
r = min(m, ry);
if (xth-i >= ) {
C[c] += move(xth-i, l, r);
}
if (xth+i <= n) {
C[c] += move(xth+i, l, r);
}
}
} void solve() {
int id; per(i, , q) {
id = draw[i].id;
xc = draw[i].xc;
yc = draw[i].yc;
w = draw[i].w;
c = draw[i].c;
h = draw[i].h;
if (id == ) {
DrawCircle();
} else if (id == ) {
DrawDiamond();
} else if (id == ) {
DrawRectangle();
} else {
DrawTriangle();
}
} rep(j, , ) {
if (j == ) {
printf("%d\n", C[j]);
} else {
printf("%d ", C[j]);
}
}
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif char op[]; while (scanf("%d %d %d", &n, &m, &q)!=EOF) {
init();
rep(i, , q) {
scanf("%s", op);
if (op[] == 'C') {
scanf("%d %d %d %d", &xc, &yc, &w, &c);
draw[i].id = ;
// DrawCircle();
} else if (op[] == 'D') {
scanf("%d %d %d %d", &xc, &yc, &w, &c);
draw[i].id = ;
// DrawDiamond();
} else if (op[] == 'R') {
scanf("%d %d %d %d %d", &xc, &yc, &h, &w, &c);
draw[i].id = ;
// DrawRectangle();
} else {
scanf("%d %d %d %d", &xc, &yc, &w, &c);
draw[i].id = ;
// DrawTriangle();
}
draw[i].xc = xc;
draw[i].yc = yc;
draw[i].h = h;
draw[i].w = w;
draw[i].c = c;
}
solve();
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}

最新文章

  1. Spring Boot
  2. 关于oracle 10g creating datafile with zero offset for aix
  3. Struts2请求参数校验
  4. NodeJS的安装
  5. selenium通过WebDriverWait实现ajax测试,实现等页面元素加载完成
  6. sql alter表字段处理
  7. web安全实战
  8. HTML头部&lt;head&gt;学习
  9. WPF之Treeview控件简单用法
  10. Python3 如何优雅地使用正则表达式(详解三)
  11. [C++程序设计]变量的存储类别
  12. GDI+ 中发生一般性错误(在 OutputStream 中保存 PNG 格式图像时遇到的问题)
  13. hdu 4870 Rating(可能性DP&amp;amp;高数消除)
  14. 51nod 修改数组
  15. 使用原始XML资源——定义原始XML资源
  16. [LeetCode] Masking Personal Information 给个人信息打码
  17. RPA答疑
  18. day 7-6 GIL,死锁,递归锁与信号量,Event,queue,
  19. Windows 8系统默认开启的.Net Framework版本是4.0,而部分用户可能需要使用到3.5或以下版本,简单添加方法
  20. jdbc:initialize-database标签的研究

热门文章

  1. php学习问题记录
  2. Spring MVC - log4j 配置
  3. 《WPF程序设计指南》读书笔记——第9章 路由输入事件
  4. 如何签名apk,并让baidu地图正常显示
  5. mac 下 sphinx + mysql + php 实现全文搜索(xampp)(3)sphinx 的配置项解析
  6. Oracle中对象权限与系统权限revoke
  7. 转:深入学习Oracle分区表及分区索引
  8. 【iOS】init,loadView,viewDidLoad加载关系
  9. 进程、线程、GDI+、XML、委托
  10. C# 的轻量级 RPC 框架