oj.uz

Submission #349194

# Submission time Handle Problem Language Result Execution time Memory
349194 2021-01-17T03:21:31 Z arnold518 Dominance (CEOI08_dominance) C++14
70 / 100
 55 ms 48000 KB 
#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(); }

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};

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

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1260 KB Output is correct
2 Correct 2 ms 2284 KB Output is correct
3 Correct 5 ms 5888 KB Output is correct
4 Runtime error 42 ms 35692 KB Memory limit exceeded
5 Runtime error 55 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 Correct 24 ms 23020 KB Output is correct
9 Runtime error 39 ms 34028 KB Memory limit exceeded
10 Runtime error 49 ms 40448 KB Memory limit exceeded
11 Runtime error 50 ms 44012 KB Memory limit exceeded
12 Correct 1 ms 492 KB Output is correct
13 Runtime error 54 ms 48000 KB Memory limit exceeded
14 Correct 1 ms 364 KB Output is correct
15 Correct 32 ms 28908 KB Output is correct
16 Correct 21 ms 21484 KB Output is correct
17 Correct 2 ms 1644 KB Output is correct
18 Correct 4 ms 4844 KB Output is correct
19 Correct 5 ms 3840 KB Output is correct
20 Correct 7 ms 6892 KB Output is correct