Submission #365327

#	Time	Username	Problem	Language	Result	Execution time	Memory
365327		kostia244	Election (BOI18_election)	C++17	100 / 100	1365 ms	59676 KiB

election

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
 
template<typename F>
void multitest(F func) {
	int t;
	cin >> t;
	while(t--) func();
}
void report(int ok) {
	cout << (ok?"YES":"NO") << '\n';
}
struct segtree {
	struct node {
		int mn, lazy;
		node() : mn(0), lazy(0) {}
		void apply(int x) {
			mn += x, lazy += x;
		}
		void push(node &l, node &r) {
			l.apply(lazy), r.apply(lazy), lazy = 0;
		}
		void build(node &l, node &r) {
			mn = min(l.mn, r.mn);
			assert(!lazy);
		}
	};
	vector<node> st;
	int n;
	segtree(int n) : st(4*n), n(n) {}
	void update(int v, int l, int r, int ql, int qr, int add) {
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr) {
			st[v].apply(add);
			return;
		}
		st[v].push(st[2*v], st[2*v+1]);
		int mid = (l+r)/2;
		update(2*v, l, mid, ql, qr, add);
		update(2*v+1, mid+1, r, ql, qr, add);
		st[v].build(st[2*v], st[2*v+1]);
	}
	void update(int l, int r, int add) { return update(1, 1, n, l, r, add); }
	int query(int v, int l, int r, int ql, int qr) {
		if(qr < l || r < ql) return 1<<30;
		if(ql <= l && r <= qr) return st[v].mn;
		st[v].push(st[2*v], st[2*v+1]);
		int mid = (l+r)/2;
		return min(query(2*v, l, mid, ql, qr), query(2*v+1, mid+1, r, ql, qr));
	}
	int query(int l, int r) { return query(1, 1, n, l, r); }
};
int n, q, a[1<<20], pref[1<<20], ans[1<<20];
vector<array<int, 2>> todo[1<<20];
segtree st(0);
int main() {
	cin.tie(0)->sync_with_stdio(0);
	//multitest([&](){});
	cin >> n;
	st = segtree(n);
	char c;
	for(int i = 1; i <= n; i++) cin >> c, a[i] = c=='C'?1:-1, pref[i] = pref[i-1]+a[i];
	cin >> q;
	for(int l, r, i = 0; i < q; i++) {
		cin >> l >> r;
		todo[r].push_back({l, i});
	}
	vector<int> bad;
	for(int i = 1; i <= n; i++) {
		st.update(i, n, a[i]);
		if(a[i] == 1 && bad.size()) {
			st.update(bad.back(), n, -1);
			bad.pop_back();
		}
		if(a[i] == -1) {
			bad.push_back(i);
			st.update(i, n, 1);
		}
		//for(auto i : bad) cout << i << " "; cout << endl;
		for(auto [l, id] : todo[i]) {
			int mn = st.query(l, i) - (l>1?st.query(l-1, l-1):0);
			ans[id] = bad.end() - lower_bound(all(bad), l);
			//cout << l << " ff " << ans[id] << endl;
			ans[id] += max(0, -mn);
		}
	}
	for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}

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