oj.uz

Submission #130463

# Submission time Handle Problem Language Result Execution time Memory
130463 2019-07-15T09:10:10 Z onjo0127 Dominance (CEOI08_dominance) C++11
100 / 100
 50 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;

struct info { int x, ys, ye, v; };

int W, H, N;
long long wc, bc;

int gety(vector<int> &S, int y) { return lower_bound(S.begin(), S.end(), y) - S.begin() + 1; }

long long getrct(int xs, int xe, int ys, int ye) {
	return 1LL * (ye - ys + 1) * (xe - xs + 1);
}

void solve(vector<info> &S) {
	sort(S.begin(), S.end(), [&](info PP, info QQ) { return PP.x < QQ.x; });
	vector<int> YS;
	for(auto& it: S) {
		YS.push_back(it.ys);
		YS.push_back(it.ye + 1);
	}
	sort(YS.begin(), YS.end()); YS.resize(unique(YS.begin(), YS.end()) - YS.begin());
	int K = YS.size();
	vector<int> C(K+1, 0);
	for(int i=0; i+1<S.size(); i++) {
		for(int j=gety(YS, S[i].ys); j<gety(YS, S[i].ye + 1); j++) C[j] += S[i].v;
		for(int j=1; j<=K; j++) {
			long long ret = getrct(S[i].x, S[i+1].x - 1, YS[j-1], YS[j]-1);
			if(C[j] < 0) bc += ret;
			if(C[j] > 0) wc += ret;
		}
	}
}

void pb(vector<info> &S, int x, int y, int r, int v) {
	S.push_back({(x+y-r) >> 1,       (-x+y-r) >> 1, (-x+y+r) >> 1, +v});
	S.push_back({((x+y+r) >> 1) + 1, (-x+y-r) >> 1, (-x+y+r) >> 1, -v});
}

int main() {
	vector<info> od, ev;
	scanf("%d%d%d",&W,&H,&N);
	for(int i=1; i<=N; i++) {
		char c; int x, y, r; scanf(" %c%d%d%d",&c,&x,&y,&r);
		int v = (c == 'W' ? +1 : -1);
		int d = (x+y+r & 1);
		pb(ev, x, y, r-d, v);
		pb(od, x, y, r+d-1, v);
	}
	solve(od);
	solve(ev);
	printf("%lld %lld", wc, bc);
	return 0;
}

Compilation message

dominance.cpp: In function 'void solve(std::vector<info>&)':
dominance.cpp:25:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i+1<S.size(); i++) {
               ~~~^~~~~~~~~
dominance.cpp: In function 'int main()':
dominance.cpp:46:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
   int d = (x+y+r & 1);
            ~~~^~
dominance.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&W,&H,&N);
  ~~~~~^~~~~~~~~~~~~~~~~~~
dominance.cpp:44:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; int x, y, r; scanf(" %c%d%d%d",&c,&x,&y,&r);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 13 ms 504 KB Output is correct
5 Correct 14 ms 504 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 14 ms 504 KB Output is correct
10 Correct 18 ms 504 KB Output is correct
11 Correct 20 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 17 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 50 ms 504 KB Output is correct
16 Correct 23 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 4 ms 376 KB Output is correct
20 Correct 5 ms 376 KB Output is correct