Submission #1264501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264501		altern23	Election (BOI18_election)	C++20	0 / 100	3 ms	576 KiB

election

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e5;
const ll INF = 4e18;
const int MOD = 1e9 + 7;

ll ps[MAXN + 5], pos[MAXN + 5];
ll cnt[MAXN + 5];

struct ST{
	ll N;
	vector<ll> sg;
	ST(ll _n){
		N = _n;
		sg.resize(4 * N + 5, INF);
	}
	
	void upd(ll l, ll r, ll cur, ll idx, ll val){
		if(l == r) sg[cur] = val;
		else{
			ll mid = (l + r) / 2;
			if(idx <= mid) upd(l, mid, cur * 2, idx, val);
			else upd(mid + 1, r, cur * 2 + 1, idx, val);
			sg[cur] = min(sg[cur * 2], sg[cur * 2 + 1]);
		}
	}
	
	ll query(ll l, ll r, ll cur, ll x, ll y){
		if(l > y || r < x) return INF;
		if(l >= x && r <= y) return sg[cur];
		ll mid = (l + r) / 2;
		return min(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
	}
};

struct BIT{
	ll N;
	vector<ll> bit;
	BIT(ll _n){
		N = _n;
		bit.resize(N + 5);
	}
	
	void upd(ll idx, ll val){
		for(; idx <= N; idx += idx & -idx) bit[idx] += val;
	}
	
	ll get(ll idx){
		ll ans = 0;
		for(; idx >= 1; idx -= idx & -idx) ans += bit[idx];
		return ans;
	}
	
	ll query(ll l, ll r){
		return get(r) - get(l - 1);
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		string S; cin >> S;
		S = '%' + S;
		
		for(int i = 1; i <= N; i++){
			ps[i] = ps[i - 1] + (S[i] == 'C' ? 1 : -1);
			cnt[i] = cnt[i - 1] + (S[i] == 'C');
		}

		stack<ll> stk;
		for(int i = N; i >= 0; --i){
			while(!stk.empty() && ps[stk.top()] >= ps[i]) stk.pop();
			if(!stk.empty()){
				pos[i] = stk.top();
			}
			stk.push(i);
		}
		
		BIT bit(N);
		ST sg(N);
		
		for(int i = 1; i <= N; i++){
			if(S[i] == 'C' && pos[i]){
				bit.upd(pos[i], 1);
				sg.upd(1, N, 1, i, -ps[pos[i] - 1]);
			}
		}
		
		ll Q; cin >> Q;
		
		vector<pii> queries[N + 5];
		vector<ll> ans(Q + 5);
		
		for(int i = 1; i <= Q; i++){
			ll l, r; cin >> l >> r;
			queries[l].push_back({r, i});
		}
		
		for(int i = 1; i <= N; i++){
			// for(int j = 1; j <= N; j++) cout << bit.query(j, j) << " ";
			// cout << "\n";
			for(auto [j, idx] : queries[i]){
				ll lf = i, rg = j, pt = i - 1;
				for(;lf <= rg;){
					ll mid = (lf + rg) / 2;
					if(ps[j] + sg.query(1, N, 1, i, mid) + j - i + 1 - cnt[j] + cnt[i - 1] - bit.query(i, mid) >= 0){
						pt = mid;
						lf = mid + 1;
					}
					else rg = mid - 1;
				}
				ans[idx] = j - i + 1 - (cnt[j] - cnt[i - 1] + bit.query(i, pt));
			}
						
			if(S[i] == 'C' && pos[i]){
				bit.upd(pos[i], -1);
				sg.upd(1, N, 1, i, INF);
			}
		}
		
		for(int i = 1; i <= Q; i++) cout << ans[i] << "\n";
	}
}

/*

*/

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