Submission #519486

#	Time	Username	Problem	Language	Result	Execution time	Memory
519486		akhan42	Election (BOI18_election)	C++17	0 / 100	7 ms	588 KiB

election

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int INF = 1000 * 1000 * 1000;

struct Seg {
	int n;
	vi add, mn;

	Seg(int n, vi &vals): n(n) {
		add.assign(4 * n, 0);
		mn.assign(4 * n, 0);

		build(vals);
	}

	void propagate(int v, int tl, int tr) {
		if(tl == tr || add[v] == 0)
			return;

		add[2 * v] += add[v];
		add[2 * v + 1] += add[v];
		mn[2 * v] += add[v];
		mn[2 * v + 1] += add[v];
		add[v] = 0;
	}

	void pull(int v) {
		mn[v] = min(mn[2 * v], mn[2 * v + 1]);
	}

	void build(vi &vals, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			mn[v] = vals[tl];
			return;
		}
		int tm = (tl + tr) / 2;

		build(vals, 2 * v, tl, tm);
		build(vals, 2 * v + 1, tm + 1, tr);

		pull(v);
	}

	void update(int l, int r, int val, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;
		propagate(v, tl, tr);
		if(l > r) return;

		if(tl == l && r == tr) {
			add[v] = val;
			mn[v] += val;
			return;
		}
		int tm = (tl + tr) / 2;

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

		pull(v);
	}

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

		if(tl == l && r == tr)
			return mn[v];
		int tm = (tl + tr) / 2;

		int ql = query(l, min(r, tm), 2 * v, tl, tm);
		int qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);

		return min(ql, qr);
	}
};


struct Seg2 {
	int n;
	vii t;

	Seg2(int n, vii &vals): n(n) {
		t.resize(4 * n);
		build(vals);
	}

	void build(vii &vals, int v = 1, int tl = 0, int tr = -1) {
		if(tr == -1) tr = n - 1;

		if(tl == tr) {
			t[v] = vals[tl];
			return;
		}
		int tm = (tl + tr) / 2;

		build(vals, 2 * v, tl, tm);
		build(vals, 2 * v + 1, tm + 1, tr);

		t[v] = min(t[2 * v], t[2 * v + 1]);
	}

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

		if(tl == l && r == tr)
			return t[v];
		int tm = (tl + tr) / 2;

		ii ql = query(l, min(r, tm), 2 * v, tl, tm);
		ii qr = query(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr);

		return min(ql, qr);
	}
};


void solve() {
	int n;
	string s;
	cin >> n >> s;
	vi pr(n), sf(n);
	forn(i, n) {
		sf[i] = pr[i] = (s[i] == 'C' ? 1 : -1);

		if(i)
			pr[i] += pr[i - 1];
	}
	for(int i = n - 2; i >= 0; i--)
		sf[i] += sf[i + 1];

	Seg sg_pr(n, pr);
	Seg sg_sf(n, sf);

	vii lr_sm;
	forn(i, n) {
		int sm = sg_sf.query(i, n - 1);
		if(i)
			sm += sg_pr.query(0, i - 1);
		lr_sm.eb(sm, i);
	}

	Seg2 sg_sm(n, lr_sm);

	int q;
	cin >> q;
	forn(_, q) {
		int l, r;
		cin >> l >> r;
		l--; r--;

		int pr_add = -(l ? pr[l - 1] : 0);
		int sf_add = -(r < n - 1 ? sf[r + 1] : 0);
		sg_pr.update(l, r, pr_add);
		sg_sf.update(l, r, sf_add);

//		int mn = INF;
//		forbn(i, l, r + 1) {
//			mineq(mn, min(0, sg_pr.query(l, i)) + min(0, sg_sf.query(i + 1, r)));
//		}

		int mn = min(0, sg_pr.query(l, r));
		mineq(mn, sg_sf.query(l, r));
//		int mn3 = 0;
//
		if(l < r) {
			int ind = sg_sm.query(l + 1, r).S;
			int mn_comb = min(0, sg_pr.query(l, ind - 1)) + min(0, sg_sf.query(ind, r));
			mineq(mn, mn_comb);
		}
//
		sg_pr.update(l, r, -pr_add);
		sg_sf.update(l, r, -sf_add);
		cout << -mn << '\n';

//		cout << -min(min(mn1, mn2), mn3) << '\n';
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("optmilk.in", "r", stdin);
//	freopen("optmilk.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

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