Submission #716480

#	Time	Username	Problem	Language	Result	Execution time	Memory
716480		lukameladze	Election (BOI18_election)	C++14	100 / 100	844 ms	50160 KiB

election

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
// #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5e5 + 5;
int t,n,a[N],sf[N],pr[N],ans[N];
int tree[4 * N], lazy[4 * N];
vector <pii> v[N];
stack <int> st;
string s;
int merge(int a, int b) {
	return min(a, b);
}
void build(int node, int le, int ri) {
	if (le == ri) {
		tree[node] = sf[le];
//		lazy[node] = 0;
		return ;
	}
	int mid = (le + ri) / 2;
	build(2 * node, le, mid);
	build(2 * node + 1, mid + 1, ri);
	tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void push(int node, int le, int ri) {
	if (!lazy[node]) return ;
	tree[node] += lazy[node];
	if (le != ri) {
    	lazy[2 * node] += lazy[node];
    	lazy[2 * node + 1] += lazy[node];
	}
	lazy[node] = 0;
}
void update(int node, int le, int ri, int start, int end, int val) {
	push(node,le,ri);
	if (le > end || ri < start) return ;
	if (le >= start && ri <= end) {
		lazy[node] = val;
		push(node,le,ri);
		return ;
	}
	int mid = (le + ri) / 2;
	update(2 * node,le,mid,start,end,val);
	update(2 * node + 1, mid + 1, ri, start, end,val);
	tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
int getans(int node, int le, int ri, int start, int end) {
	push(node,le,ri);
	if (le > end || ri < start) return 1e9;
	if (le >= start && ri <= end) {
		return tree[node];
	}
	int mid = (le + ri) / 2;
	return merge(getans(2 * node, le, mid,start,end), getans(2 * node + 1, mid + 1, ri, start, end));
}
int tree_f[N];
void upd(int idx, int val) {
//	cout<<"upd "<<idx<<" "<<val<<"\n";
	for (int i = idx; i < N; i+=i&(-i)) {
		tree_f[i] += val;
	}
}
int get(int idx) {
	int pas = 0;
	
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree_f[i];
	}
	return pas;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>s; s = "@" + s;
	for (int i = 1; i <= n; i++) {
		pr[i] = pr[i - 1] + (s[i] == 'C' ? 1 : -1);
	}
	for (int i = n; i >= 1; i--) {
		sf[i] = sf[i + 1] + (s[i] == 'C' ? 1 : -1);
	}
	build(1, 1, n);
	int q; cin>>q;
	for (int i = 1; i <= q; i++) {
		int l, r; cin>>l>>r;
		v[l].pb({r, i});
	}	
	for (int i = n; i >= 1; i--) {
		if (s[i] == 'T') {
			st.push(i); update(1, 1, n, 1, i, 1); upd(i, 1);
		} else {
			if (!st.empty()) {
				int x = st.top(); st.pop();
				update(1, 1, n, 1, x, -1); upd(x, -1);
			}
		}
		for (pii sth : v[i]) {
			int ri = sth.f; int id = sth.s;
			ans[id] = get(ri) + max(0, -(getans(1,1, n, i, ri) - sf[ri + 1] - get(n) + get(ri)));
		}
	}
	for (int i = 1; i <= q; i++) {
		cout<<ans[i]<<"\n";
	}
}

Compilation message (stderr)

election.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main() {
      | ^~~~

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