제출 #137727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137727		math0_0	Election (BOI18_election)	C++11	0 / 100	98 ms	94300 KiB

election

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pi;

#define MX 2000010
#define fi first
#define se second

pair<pair<pi, pi>, pi> st[MX];//((nullify left, nullify right), range)
ll pos[MX] = {0};

#define INF 1000000007

ll querylf(ll l, ll r){
	--l; --r;
	//querying the st
	ll cseg = pos[l], nul = 0, rm = 0;
	bool wincon = true;
	vector<ll> idx;
	
	while(wincon){
		wincon = (st[cseg].se.se != r);
		
		if(cseg%2==0){
			if(st[cseg].se.se < r){
				cseg/=2;
			}
			else if(st[cseg].se.se == r){
				idx.push_back(cseg);
			}
			else{
				if(st[2*cseg].se.se < r){
					idx.push_back(2*cseg);
					cseg*=2;
					cseg++;
				}
				else{
					cseg*=2;
				}	
			}
		}
		else{
			if(st[cseg].se.se < r){
				idx.push_back(cseg);
				cseg-=1;
				cseg/=2;
				cseg++;
			}
			else if(st[cseg].se.se == r){
				idx.push_back(cseg);
			}
			else{
				if(st[2*cseg].se.se < r){
					idx.push_back(2*cseg);
					cseg*=2;
					cseg++;
				}
				else{
					cseg*=2;
				}
			}
		}
	}
	
	//now process all in idx
	for(ll two = 0; two < idx.size(); two++){			
		ll tp = rm - st[idx[two]].fi.fi.fi;
		if(tp >= 0){rm+=tp;}
		else{
			rm = st[idx[two]].fi.fi.se;
			nul -= tp;
		}
	}
	
	return nul;
}

ll queryrt(ll l, ll r){
	--l; --r;
	//querying the st
	ll cseg = pos[l], nul = 0, rm = 0;
	bool wincon = true;
	vector<ll> idx;
	
	while(wincon){
		wincon = (st[cseg].se.se != r);
		
		if(cseg%2==0){
			if(st[cseg].se.se < r){
				cseg/=2;
			}
			else if(st[cseg].se.se == r){
				idx.push_back(cseg);
			}
			else{
				if(st[2*cseg].se.se < r){
					idx.push_back(2*cseg);
					cseg*=2;
					cseg++;
				}
				else{
					cseg*=2;
				}	
			}
		}
		else{
			if(st[cseg].se.se < r){
				idx.push_back(cseg);
				cseg-=1;
				cseg/=2;
				cseg++;
			}
			else if(st[cseg].se.se == r){
				idx.push_back(cseg);
			}
			else{
				if(st[2*cseg].se.se < r){
					idx.push_back(2*cseg);
					cseg*=2;
					cseg++;
				}
				else{
					cseg*=2;
				}
			}
		}
	}
	
	//now process all in idx
	for(ll two = idx.size()-1; two > -1; --two){
		ll tp = rm - st[idx[two]].fi.se.fi;
		if(tp >= 0){rm+=tp;}
		else{
			rm = st[idx[two]].fi.se.se;
			nul -= tp;
		}
	}
	
	return nul;
}

int main(){
	ll n;
	cin >> n;
	
	string vote;
	cin >> vote;
	
	//initialise segtree?
	pi pinf = make_pair(INF, 0);
	st[1] = make_pair(make_pair(pinf, pinf), make_pair(0, n-1));
	for(ll one = 2; one < MX; one++){
		st[one] = make_pair(make_pair(pinf, pinf), make_pair(-1, -1));
	}
	for(ll one = 1; one < MX; one++){
		if(st[one].se.fi != st[one].se.se){
			ll md = st[one].se.fi+st[one].se.se;
			md/=2;
			st[2*one] = make_pair(make_pair(pinf, pinf), make_pair(st[one].se.fi, md));
			st[2*one+1] = make_pair(make_pair(pinf, pinf), make_pair(md+1, st[one].se.se));
		}
		else{
			if(pos[st[one].se.fi] == 0){
				pos[st[one].se.fi] = one;
			}
		}
	}
	
	//calculate segtree
	ll mbk = 0;
	for(ll one = 0; one < n; one++){
		ll blk = pos[one];
		mbk = max(mbk, blk);
		if(vote[one] == 'C'){
			st[blk].fi.fi.fi = 0;
			st[blk].fi.fi.se = 1;
			st[blk].fi.se.fi = 0;
			st[blk].fi.se.se = 1;
		}
		else{
			st[blk].fi.fi.fi = 1;
			st[blk].fi.fi.se = 0;
			st[blk].fi.se.fi = 1;
			st[blk].fi.se.se = 0;
		}
	}
	
	for(ll one = mbk; one > 1; one-=2){
		if(st[one].fi.fi.fi < INF){
			ll tbk = (one-1)/2;
			st[tbk].fi.fi.fi = st[one-1].fi.fi.fi;
			
			ll tp = st[one-1].fi.fi.se - st[one].fi.fi.fi;
			if(tp >= 0){st[tbk].fi.fi.se = tp + st[one].fi.fi.se;}
			else{
				st[tbk].fi.fi.se = st[one].fi.fi.se;
				st[tbk].fi.fi.fi -= tp;
			}
			
			st[tbk].fi.se.fi = st[one].fi.se.fi;
			tp = st[one].fi.se.se - st[one-1].fi.se.fi;
			if(tp >= 0){st[tbk].fi.se.se = tp+st[one-1].fi.se.se;}
			else{
				st[tbk].fi.se.se = st[one-1].fi.se.se;
				st[tbk].fi.se.fi -= tp;
			}
		}
	}


	
	ll q;
	cin >> q;
	
	ll l, r;
	for(ll one = 0; one < q; one++){
		cin >> l >> r;
		cout << max(querylf(l, r), queryrt(l, r)) << endl;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

election.cpp: In function 'll querylf(ll, ll)':
election.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll two = 0; two < idx.size(); two++){   
                  ~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18