Submission #648746

#	Time	Username	Problem	Language	Result	Execution time	Memory
648746		GusterGoose27	Election (BOI18_election)	C++11	100 / 100	831 ms	91796 KiB

election

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 5e5;
const int inf = 1e9;
int n, q;
vector<pii> ranges[MAXN];
int pre[MAXN+1];

pii operator+(pii a, pii b) {
	return pii(a.first+b.first, a.second+b.second);
}

class stree {
public:
	int lz = 0, mxh = -inf;
	// int sum = 0;
	stree *l = nullptr;
	stree *r = nullptr;
	int lp, rp;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp == rp) {
			mxh = pre[lp];
		}
		else {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
			mxh = max(l->mxh, r->mxh);
		}
	}
	// pii query(int lv, int rv) { // height, sum
	// 	if (lp > rv || rp < lv) return pii(0, 0);
	// 	if (lp >= rv && rp <= rv) return pii(mxh, sum);
	// 	return l->query(lv, rv)+r->query(lv, rv)+pii(lz, 0);
	// }
	int query(int lv, int rv) { // height, sum
		if (lp > rv || rp < lv) return -inf;
		if (lp >= lv && rp <= rv) return mxh;
		return max(l->query(lv, rv), r->query(lv, rv))+lz;
	}
	void height_update(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			lz += v;
			mxh += v;
			return;
		}
		l->height_update(lv, rv, v);
		r->height_update(lv, rv, v);
		mxh = lz+max(l->mxh, r->mxh);
	}
	// void sum_upd(int p, int v) {
	// 	if (lp > p || rp < p) return;
	// 	if (lp == rp) {
	// 		sum += v;
	// 		return;
	// 	}
	// 	l->sum_upd(p, v);
	// 	r->sum_upd(p, v);
	// 	sum = l->sum+r->sum;
	// }
};

stree *tree;
vector<pii> queries[MAXN]; // right point, id
int qansws[MAXN];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	string s; cin >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'C') pre[i+1] = pre[i]+1;
		else pre[i+1] = pre[i]-1;
	}
	tree = new stree(0, n);
	cin >> q;
	for (int i = 0; i < q; i++) {
		int l, r; cin >> l >> r; l--;
		queries[l].push_back(pii(r, i));
	}
	vector<int> mon_stack;
	mon_stack.push_back(n);
	for (int i = n-1; i >= 0; i--) {
		if (pre[i] > pre[i+1]) {
			// tree->sum_upd(i+1, -1);
			tree->height_update(i+2, n, 1);
		}
		else {
			mon_stack.pop_back();
			if (!mon_stack.empty()) {
				int nxt = mon_stack.back();
				// tree->sum_upd(nxt, 1);
				tree->height_update(nxt+1, n, -1);
				mon_stack.pop_back();
			}
		}
		mon_stack.push_back(i);
		for (pii p: queries[i]) {
			qansws[p.second] = tree->query(i, p.first)-pre[p.first];
		}
	}
	for (int i = 0; i < q; i++) cout << qansws[i] << "\n";
}

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