Submission #130463

#	Time	Username	Problem	Language	Result	Execution time	Memory
130463		onjo0127	Dominance (CEOI08_dominance)	C++11	100 / 100	50 ms	504 KiB

dominance

#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 (stderr)

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 / 100