#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<int> xcomp, ycomp;
int getx(int x) { return lower_bound(xcomp.begin(), xcomp.end(), x)-xcomp.begin(); }
int gety(int y) { return lower_bound(ycomp.begin(), ycomp.end(), y)-ycomp.begin(); }
int P[MAXN+10][MAXN+10], Q[MAXN+10][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};
int 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++)
{
int x=A[i].x-A[i].y, y=A[i].x+A[i].y;
P[getx(x-A[i].r)][gety(y-A[i].r)]++;
P[getx(x+A[i].r+1)][gety(y-A[i].r)]--;
P[getx(x-A[i].r)][gety(y+A[i].r+1)]--;
P[getx(x+A[i].r+1)][gety(y+A[i].r+1)]++;
}
for(int i=1; i<=NB; i++)
{
int x=B[i].x-B[i].y, y=B[i].x+B[i].y;
Q[getx(x-B[i].r)][gety(y-B[i].r)]++;
Q[getx(x+B[i].r+1)][gety(y-B[i].r)]--;
Q[getx(x-B[i].r)][gety(y+B[i].r+1)]--;
Q[getx(x+B[i].r+1)][gety(y+B[i].r+1)]++;
}
for(int i=1; i<=SX; i++) for(int j=1; j<=SY; j++)
{
P[i][j]+=P[i-1][j]+P[i][j-1]-P[i-1][j-1];
Q[i][j]+=Q[i-1][j]+Q[i][j-1]-Q[i-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][j]>Q[i][j]) ans1+=t;
else if(P[i][j]<Q[i][j]) ans2+=t;
}
printf("%lld %lld\n", ans1, ans2);
}
Compilation message
dominance.cpp: In function 'int main()':
dominance.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
27 | scanf("%*d%*d");
| ~~~~~^~~~~~~~~~
dominance.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
28 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
dominance.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
38 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
dominance.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf("%d%d%d", &x, &y, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2292 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5888 KB |
Output is correct |
| 4 |
Runtime error |
42 ms |
35564 KB |
Memory limit exceeded |
| 5 |
Runtime error |
58 ms |
47852 KB |
Memory limit exceeded |
| 6 |
Correct |
1 ms |
1260 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1772 KB |
Output is correct |
| 8 |
Incorrect |
25 ms |
23020 KB |
Output isn't correct |
| 9 |
Runtime error |
39 ms |
34028 KB |
Memory limit exceeded |
| 10 |
Runtime error |
46 ms |
40300 KB |
Memory limit exceeded |
| 11 |
Runtime error |
52 ms |
43884 KB |
Memory limit exceeded |
| 12 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 13 |
Runtime error |
56 ms |
47852 KB |
Memory limit exceeded |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
32 ms |
28928 KB |
Output is correct |
| 16 |
Correct |
22 ms |
21496 KB |
Output is correct |
| 17 |
Correct |
2 ms |
1644 KB |
Output is correct |
| 18 |
Incorrect |
4 ms |
4844 KB |
Output isn't correct |
| 19 |
Correct |
4 ms |
3712 KB |
Output is correct |
| 20 |
Correct |
7 ms |
6892 KB |
Output is correct |
