oj.uz

Submission #854780

# Submission time Handle Problem Language Result Execution time Memory
854780 2023-09-28T20:42:04 Z TadijaSebez Dominance (CEOI08_dominance) C++17
100 / 100
 30 ms 736 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const ll lim=2e9;

const int N=3050;
int x[N],y[N],r[N];
char col[N];

ll Get(ll L,ll R,ll diff){
	if(abs(L)%2!=diff%2)L++;
	if(abs(R)%2!=diff%2)R--;
	if(L>R)return 0;
	return (R-L+2)/2;
}

void Split(vector<array<ll,3>>& all,ll val){
	vector<array<ll,3>> ans;
	for(auto x:all){
		if(x[0]<=val && x[1]>=val){
			if(x[0]<val){
				ans.pb({x[0],val-1,x[2]});
				ans.pb({val,x[1],x[2]});
			}else{
				ans.pb(x);
			}
		}else{
			ans.pb(x);
		}
	}
	all=ans;
}
int main(){
	int n;
	scanf("%*i %*i %i",&n);
	vector<pair<int,int>> evs;
	for(int i=1;i<=n;i++){
		scanf("\n%c %i %i %i",&col[i],&x[i],&y[i],&r[i]);
		evs.pb({x[i]+y[i]-r[i],-i});
		evs.pb({x[i]+y[i]+r[i]+1,i});
	}
	sort(evs.begin(),evs.end());
	vector<array<ll,3>> all;
	all.pb({-lim,lim,0});
	ll last=2;
	ll W=0,B=0;
	for(auto ev:evs){
		int i=abs(ev.second);
		ll diff=ev.first-last;

		ll even=(diff+1)/2;
		ll odd=diff/2;

		for(auto x:all){
			ll add=even*Get(x[0],x[1],last)+odd*Get(x[0],x[1],last+1);
			if(x[2]!=0){
				//printf("add:%lld e:%lld o:%lld  [%lld %lld]\n",add,Get(x[0],x[1],last),Get(x[0],x[1],last+1),x[0],x[1]);
			}
			if(x[2]>0)W+=add;
			else if(x[2]<0)B+=add;
		}
		//printf("i:%i W:%lld B:%lld diff:%lld even:%lld odd:%lld\n",i,W,B,diff,even,odd);

		ll add=col[i]=='W'?1:-1;
		if(ev.second>0){
			add=-add;
		}

		ll L=x[i]-y[i]-r[i];
		ll R=x[i]-y[i]+r[i];
		Split(all,L);
		Split(all,R+1);
		for(auto &x:all){
			if(x[0]>=L && x[1]<=R){
				x[2]+=add;
			}
		}

		last=ev.first;
	}
	printf("%lld %lld\n",W,B);
	return 0;
}

Compilation message

dominance.cpp: In function 'int main()':
dominance.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%*i %*i %i",&n);
      |  ~~~~~^~~~~~~~~~~~~~~~~
dominance.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("\n%c %i %i %i",&col[i],&x[i],&y[i],&r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 500 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 18 ms 688 KB Output is correct
5 Correct 26 ms 712 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 10 ms 604 KB Output is correct
9 Correct 18 ms 676 KB Output is correct
10 Correct 25 ms 708 KB Output is correct
11 Correct 25 ms 716 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 26 ms 736 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 30 ms 696 KB Output is correct
16 Correct 19 ms 604 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 3 ms 348 KB Output is correct
20 Correct 3 ms 444 KB Output is correct