#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 6000;
struct Data
{
int x, y, r;
};
int N, NA, NB, SX, SY;
Data A[MAXN+10], B[MAXN+10];
vector<ll> xcomp, ycomp;
int getx(ll x) { return lower_bound(xcomp.begin(), xcomp.end(), x)-xcomp.begin(); }
int gety(ll y) { return lower_bound(ycomp.begin(), ycomp.end(), y)-ycomp.begin(); }
vector<pii> VP[MAXN+10], VQ[MAXN+10];
int P[2][MAXN+10], Q[2][MAXN+10];
ll ans1=0, ans2=0;
int main()
{
scanf("%*d%*d");
scanf("%d", &N);
xcomp.push_back(-2147483648);
ycomp.push_back(-2147483648);
xcomp.push_back(2147483647);
ycomp.push_back(2147483647);
for(int i=1; i<=N; i++)
{
int x, y, r;
char c;
scanf(" %c", &c);
scanf("%d%d%d", &x, &y, &r);
if(c=='W') A[++NA]={x, y, r};
else B[++NB]={x, y, r};
ll x2=x-y, y2=x+y;
xcomp.push_back(x2-r);
ycomp.push_back(y2-r);
xcomp.push_back(x2+r+1);
ycomp.push_back(y2+r+1);
}
sort(xcomp.begin(), xcomp.end());
xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
sort(ycomp.begin(), ycomp.end());
ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
SX=xcomp.size()-2;
SY=ycomp.size()-2;
for(int i=1; i<=NA; i++)
{
ll x=A[i].x-A[i].y, y=A[i].x+A[i].y;
VP[getx(x-A[i].r)].push_back({gety(y-A[i].r), 1});
VP[getx(x+A[i].r+1)].push_back({gety(y-A[i].r), -1});
VP[getx(x-A[i].r)].push_back({gety(y+A[i].r+1), -1});
VP[getx(x+A[i].r+1)].push_back({gety(y+A[i].r+1), 1});
}
for(int i=1; i<=NB; i++)
{
ll x=B[i].x-B[i].y, y=B[i].x+B[i].y;
VQ[getx(x-B[i].r)].push_back({gety(y-B[i].r), 1});
VQ[getx(x+B[i].r+1)].push_back({gety(y-B[i].r), -1});
VQ[getx(x-B[i].r)].push_back({gety(y+B[i].r+1), -1});
VQ[getx(x+B[i].r+1)].push_back({gety(y+B[i].r+1), 1});
}
for(int i=1; i<=SX; i++)
{
for(int j=0; j<=SY; j++) P[i&1][j]=0, Q[i&1][j]=0;
for(auto it : VP[i]) P[i&1][it.first]+=it.second;
for(auto it : VQ[i]) Q[i&1][it.first]+=it.second;
for(int j=1; j<=SY; j++)
{
P[i&1][j]+=P[i-1&1][j]+P[i&1][j-1]-P[i-1&1][j-1];
Q[i&1][j]+=Q[i-1&1][j]+Q[i&1][j-1]-Q[i-1&1][j-1];
ll t=(xcomp[i+1]-xcomp[i])*(ycomp[j+1]-ycomp[j]);
if(t%2==0) t/=2;
else if((xcomp[i]+ycomp[j])%2) t=t/2;
else t=(t+1)/2;
if(P[i&1][j]>Q[i&1][j]) ans1+=t;
else if(P[i&1][j]<Q[i&1][j]) ans2+=t;
}
}
printf("%lld %lld\n", ans1, ans2);
}
Compilation message
dominance.cpp: In function 'int main()':
dominance.cpp:86:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
86 | P[i&1][j]+=P[i-1&1][j]+P[i&1][j-1]-P[i-1&1][j-1];
| ~^~
dominance.cpp:86:42: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
86 | P[i&1][j]+=P[i-1&1][j]+P[i&1][j-1]-P[i-1&1][j-1];
| ~^~
dominance.cpp:87:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
87 | Q[i&1][j]+=Q[i-1&1][j]+Q[i&1][j-1]-Q[i-1&1][j-1];
| ~^~
dominance.cpp:87:42: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
87 | Q[i&1][j]+=Q[i-1&1][j]+Q[i&1][j-1]-Q[i-1&1][j-1];
| ~^~
dominance.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | scanf("%*d%*d");
| ~~~~~^~~~~~~~~~
dominance.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
29 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
dominance.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
dominance.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | scanf("%d%d%d", &x, &y, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
748 KB |
Output is correct |
| 2 |
Correct |
1 ms |
620 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| 4 |
Correct |
19 ms |
748 KB |
Output is correct |
| 5 |
Correct |
29 ms |
768 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
620 KB |
Output is correct |
| 8 |
Correct |
11 ms |
748 KB |
Output is correct |
| 9 |
Correct |
18 ms |
768 KB |
Output is correct |
| 10 |
Correct |
23 ms |
748 KB |
Output is correct |
| 11 |
Correct |
24 ms |
748 KB |
Output is correct |
| 12 |
Correct |
1 ms |
620 KB |
Output is correct |
| 13 |
Correct |
25 ms |
748 KB |
Output is correct |
| 14 |
Correct |
1 ms |
620 KB |
Output is correct |
| 15 |
Correct |
16 ms |
748 KB |
Output is correct |
| 16 |
Correct |
10 ms |
748 KB |
Output is correct |
| 17 |
Correct |
1 ms |
620 KB |
Output is correct |
| 18 |
Correct |
2 ms |
620 KB |
Output is correct |
| 19 |
Correct |
2 ms |
620 KB |
Output is correct |
| 20 |
Correct |
4 ms |
620 KB |
Output is correct |
