Submission #578381

#	Time	Username	Problem	Language	Result	Execution time	Memory
578381		AlperenT	Election (BOI18_election)	C++17	100 / 100	1874 ms	50032 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5, INF = 1e9 + 5;

int n, q, l, r, ans[N], mn;

char arr[N];

vector<pair<int, int>> query[N];

stack<int> stk;

// bool vis[N];

struct Fenwick{
	int tree[N];

	int query(int pos){
		int sum = 0;
		for(int i = pos; i > 0; i -= i & -i) sum += tree[i];
		return sum;
	}

	void update(int pos, int val){
		for(int i = pos; i < N; i += i & -i) tree[i] += val;
	}

	void range_update(int l, int r, int val){
		if(l <= r){
			update(l, val);
			update(r + 1, -val);
		}
	}
};

Fenwick fw;

struct SegTree{
	int tree[N * 4], lazy[N * 4];

	int merge(int a, int b){
		return max(a, b);
	}

	void push(int v){
		if(lazy[v]){
			tree[v] += lazy[v];

			if(v * 2 < N * 4) lazy[v * 2] += lazy[v], lazy[v * 2 + 1] += lazy[v];

			lazy[v] = 0;
		}
	}

	void update(int l, int r, int val, int v = 1, int tl = 1, int tr = n){
		if(l > r) return;
		else if(tl == l && tr == r) lazy[v] += val;
		else{
			push(v);

			int tm = tl + (tr - tl) / 2;

			update(l, min(tm, r), val, v * 2, tl, tm);
			update(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);

			push(v * 2), push(v * 2 + 1);

			tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
		}
	}

	int query(int l, int r, int v = 1, int tl = 1, int tr = n){
		if(l > r) return -INF;

		push(v);

		if(l == tl && r == tr) return tree[v];
		else{
			int tm = tl + (tr - tl) / 2;

			return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
		}
	}
};

SegTree sgt;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	cin >> n;

	for(int i = 1; i <= n; i++) cin >> arr[i];

	cin >> q;

	for(int i = 1; i <= q; i++){
		cin >> l >> r;

		query[l].push_back({r, i});
	}

	mn = INF;

	for(int i = n; i >= 1; i--){
		if(arr[i] == 'C'){
			sgt.update(i, n, 1);

			if(!stk.empty()){
				sgt.update(stk.top(), n, -1);

				if(mn != INF){
					sgt.update(stk.top(), n, -sgt.query(i, stk.top() - 1));

					int l = stk.top() - 1, r = n + 1, m;

					while(r - l > 1){
						m = l + (r - l) / 2;

						if(sgt.query(stk.top(), m) >= 0) r = m;
						else l = m;
					}

					fw.range_update(r, n, -1);

					sgt.update(stk.top(), n, sgt.query(i, stk.top() - 1));
				}

				stk.pop();
			}
		}
		else if(arr[i] == 'T'){
			mn = i;

			fw.range_update(i, n, 1);

			stk.push(i);
		}

		for(auto p : query[i]){
			ans[p.second] = fw.query(p.first);
		}
	}

	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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