Submission #290712

#	Time	Username	Problem	Language	Result	Execution time	Memory
290712		Gurban	Election (BOI18_election)	C++17	100 / 100	1799 ms	61200 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 5e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n,q,M[4*maxn][3],T[4*maxn][3],ans[maxn];
string s;
stack<int>last;

void prop(int tp,int nd){
	if(tp==0){
		T[nd*2][0] += T[nd][1];
		T[nd*2][1] += T[nd][1];
		T[nd*2+1][0] += T[nd][1];
		T[nd*2+1][1] += T[nd][1];
		T[nd][1] = 0;
	}
	else {
		M[nd*2][0] += M[nd][1];
		M[nd*2][1] += M[nd][1];
		M[nd*2+1][0] += M[nd][1];
		M[nd*2+1][1] += M[nd][1];
		M[nd][1] = 0;
	}
}	

void upd(int val,int a,int b,int l,int r,int nd){
	if(r < a or l > b) return;
	if(l >= a and r <= b){T[nd][0] += val,T[nd][1] += val;return;}
	
	prop(0,nd);
	upd(val,a,b,l,(l+r)/2,nd*2);
	upd(val,a,b,(l+r)/2+1,r,nd*2+1);

	T[nd][0]=min(T[nd*2][0],T[nd*2+1][0]);
}

int tap(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return mod;
	if(l >= a and r <= b) return T[nd][0];
	prop(0,nd);
	return min(tap(a,b,l,(l+r)/2,nd*2),tap(a,b,(l+r)/2+1,r,nd*2+1));
}

void upd1(int val,int a,int b,int l,int r,int nd){
	if(r < a or l > b) return;
	if(l >= a and r <= b){M[nd][0] += val,M[nd][1] += val;return;}
	
	prop(1,nd);
	upd1(val,a,b,l,(l+r)/2,nd*2);
	upd1(val,a,b,(l+r)/2+1,r,nd*2+1);

	M[nd][0]=max(M[nd*2][0],M[nd*2+1][0]);
}

int tap1(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return 0;
	if(l >= a and r <= b) return M[nd][0];
	prop(1,nd);
	return max(tap1(a,b,l,(l+r)/2,nd*2),tap1(a,b,(l+r)/2+1,r,nd*2+1));
}

int main(){
	#ifdef LOCAL
		clock_t TSTART = clock();
	#endif
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> s >> q;
	vector<pii>v[n];
	int a,b;
	for(int i = 0;i < q;i++){
		cin >> a >> b;
		v[a-1].pb({b-1,i});
	}

	// for(int i = n-1;i >= 0;i--){
	// 	if(sz(v[i])){
	// 		cout<<i<<" ---> ";
	// 		for(auto j : v[i]) cout<<j.ff<<' ';
	// 		cout<<'\n';
	// 	}
	// }
	for(int i = n-1;i >= 0;i--){
		if(s[i]=='C'){
			upd(1,i,n-1,0,n-1,1);
			upd1(1,i,n-1,0,n-1,1);
			if(!last.empty()){
				int pos=last.top(); 
				last.pop();
				upd1(-1,pos,n-1,0,n-1,1);
			}
		}
		else {
			upd(-1,i,n-1,0,n-1,1);
			last.push(i);
		}
		// for(int j = 0;j < n;j++) cout<<tap1(j,j,0,n-1,1)<<' ';
		// cout<<'\n';
		for(auto j : v[i]){
			a = tap(i,j.ff,0,n-1,1);
			b = tap1(i,j.ff,0,n-1,1);
			int val = tap1(j.ff,j.ff,0,n-1,1);
			// cout<<a<<' '<<b<<' '<<val<<'\n';
			ans[j.ss]=b-val-min(0,a);
		}
	}
	for(int i = 0;i < q;i++) cout<<ans[i]<<'\n';

	#ifdef LOCAL
		cout << "\nTime elapsed: " << double(clock()-TSTART) / CLOCKS_PER_SEC << " s.\n";
	#endif
}

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