oj.uz

답안 #349193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349193 2021-01-17T03:20:16 Z arnold518 Dominance (CEOI08_dominance) C++14
55 / 100
 58 ms 47852 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<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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
55.0 / 100.0

# 결과 실행 시간 메모리 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