Submission #574513

#	Time	Username	Problem	Language	Result	Execution time	Memory
574513		FatihSolak	Election (BOI18_election)	C++17	100 / 100	766 ms	56412 KiB

election

#include <bits/stdc++.h>
#define N 500005
using namespace std;
vector<pair<int,int>> query[N];
int ans[N];
int suf[N];
struct SegTree{
	vector<int> t,lazy;
	int n;
	SegTree(int size){
		n = size;
		t.assign(4*n,1e9);
		lazy.assign(4*n,0);
	}
	void push(int v){
		t[v*2] += lazy[v];
		lazy[v*2] += lazy[v];
		t[v*2+1] += lazy[v];
		lazy[v*2+1] += lazy[v];
		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r < tl)
			return;
		if(l <= tl && tr <= r){
			t[v] += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v*2+1,tm+1,tr,l,r,val);
		t[v] = min(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return 1e9;
		if(l <= tl && tr <= r)
			return t[v];
		push(v);
		int tm = (tl + tr)/2;
		return min(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int l,int r,int val){
		upd(1,1,n,l,r,val);
	}
	int get(int l,int r){
		return get(1,1,n,l,r);
	}
};
struct BIT{
	vector<int> bit;
	int n;
	BIT(int size){
		n = size + 5;
		bit.assign(n,0);
	}
	void upd(int pos,int val){
		for(;pos < n;pos += pos & -pos)
			bit[pos] += val;
	}
	int get(int pos){
		int ret = 0;
		for(;pos > 0;pos -= pos & -pos)
			ret += bit[pos];
		return ret;
	}
	int get(int l,int r){
		return get(r) - get(l-1);
	}
};
void solve(){
	int n,q;
	string s;
	cin >> n >> s >> q;
	s = "." + s;
	for(int i = n;i>=1;i--){
		suf[i] = suf[i+1] + (s[i] =='C'?1:-1);
		//cout << i << " " << suf[i] << endl;	
	}
	for(int i = 1;i<=q;i++){
		int l,r;
		cin >> l >> r;
		query[l].push_back({r,i});
	}
	SegTree t(n);
	BIT bt(n);
	vector<int> nodes;
	for(int i = n;i>=1;i--){
		if(s[i] == 'C'){
			if(nodes.size()){
				bt.upd(nodes.back(),-1);
				t.upd(i+1,nodes.back(),-1);
				nodes.pop_back();
			}
		}
		if(s[i] == 'T'){
			bt.upd(i,1);
			nodes.push_back(i);
		}
		t.upd(i,i,(int) - 1e9 + suf[i] + nodes.size());
		for(auto u:query[i]){
			int tot = bt.get(i,u.first);
			tot += max(0,-(t.get(i,u.first) - suf[u.first+1] - bt.get(u.first+1,n)));
			ans[u.second] = tot;
		}	
		/*
		cout << "i: " << i << endl;	
		for(int j = i;j<=n;j++){
			cout << t.get(j,j) << " ";
		}
		cout << endl;*/
	}
	for(int i = 1;i<=q;i++){
		cout << ans[i] << "\n";
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	#ifdef Local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	#ifdef Local
		cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
	#endif
}

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