oj.uz

Submission #349190

# Submission time Handle Problem Language Result Execution time Memory
349190 2021-01-17T03:14:40 Z arnold518 Dominance (CEOI08_dominance) C++14
0 / 100
 53 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;
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 x) { return lower_bound(ycomp.begin(), ycomp.end(), x)-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());

	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<xcomp.size(); i++) for(int j=1; j<ycomp.size(); 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(P[i][j]>Q[i][j]) ans1+=t;
		else if(P[i][j]<Q[i][j]) ans2+=t;
	}
	printf("%lld %lld\n", (ans1+1)/2, (ans2+1)/2);
}

Compilation message

dominance.cpp: In function 'int main()':
dominance.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=1; i<xcomp.size(); i++) for(int j=1; j<ycomp.size(); j++)
      |               ~^~~~~~~~~~~~~
dominance.cpp:74:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for(int i=1; i<xcomp.size(); i++) for(int j=1; j<ycomp.size(); j++)
      |                                                 ~^~~~~~~~~~~~~
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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1260 KB Output isn't correct
2 Incorrect 2 ms 2284 KB Output isn't correct
3 Incorrect 5 ms 5868 KB Output isn't correct
4 Runtime error 36 ms 35692 KB Memory limit exceeded
5 Runtime error 53 ms 47852 KB Memory limit exceeded
6 Incorrect 1 ms 1388 KB Output isn't correct
7 Incorrect 2 ms 1772 KB Output isn't correct
8 Incorrect 26 ms 23020 KB Output isn't correct
9 Runtime error 37 ms 34044 KB Memory limit exceeded
10 Runtime error 42 ms 40300 KB Memory limit exceeded
11 Runtime error 46 ms 44012 KB Memory limit exceeded
12 Incorrect 1 ms 492 KB Output isn't correct
13 Runtime error 50 ms 47852 KB Memory limit exceeded
14 Incorrect 1 ms 492 KB Output isn't correct
15 Incorrect 29 ms 28908 KB Output isn't correct
16 Incorrect 21 ms 21504 KB Output isn't correct
17 Incorrect 2 ms 1644 KB Output isn't correct
18 Incorrect 4 ms 4844 KB Output isn't correct
19 Incorrect 4 ms 3820 KB Output isn't correct
20 Incorrect 6 ms 6892 KB Output isn't correct