Submission #349195

#	Time	Username	Problem	Language	Result	Execution time	Memory
349195		arnold518	Dominance (CEOI08_dominance)	C++14	100 / 100	29 ms	768 KiB

dominance

#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 (stderr)

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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100