Submission #349193

#	Time	Username	Problem	Language	Result	Execution time	Memory
349193		arnold518	Dominance (CEOI08_dominance)	C++14	55 / 100	58 ms	47852 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<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 (stderr)

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

• Subtask 1: 55 / 100