Submission #1096551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096551		vjudge1	Election (BOI18_election)	C++98	100 / 100	368 ms	36612 KiB

election

#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define IOS      ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F        first
#define S        second
#define sz(x)    int(x.size())
#define all(x)   x.begin(), x.end()
#define pb       push_back

const int Inf    = 2e9 + 10;
const int Mod    = 1e9 + 7;
const int LG     = 25;
const int SQ     = 400;
const int Alpha  = 27;
const int maxN   = 5e5 + 10;

int n, q;
int a[maxN];

struct SegTree {
	struct Node {
		int sum;
		int mnLR;
		int mnRL;
		int ans;
		Node() {
			sum = mnLR = mnRL = ans = 0;
		}
	} t[maxN<<2];
	
	Node Merge(Node lc, Node rc) {
		Node ret;
		ret.sum = lc.sum + rc.sum;
		ret.mnLR = min(lc.mnLR, lc.sum + rc.mnLR);
		ret.mnRL = min(rc.mnRL, rc.sum + lc.mnRL);
		ret.ans = max( -(lc.mnLR + rc.mnRL), max(lc.ans - rc.sum, rc.ans - lc.sum));
		return ret;
	}

	void initialize(int id, int L, int R) {
		if(L+1 == R) {
			t[id].sum = a[L];
			t[id].mnLR = min(0, a[L]);
			t[id].mnRL = min(0, a[L]);
			t[id].ans = abs(min(0, a[L]));
			return;
		}

		int mid = (L+R)>>1;
		initialize(2*id+0, L, mid);
		initialize(2*id+1, mid, R);
		
		t[id] = Merge(t[2*id+0], t[2*id+1]);
	}

	Node Get(int id, int L, int R, int l, int r) {
		if(L == l and R == r)
			return t[id];

		int mid = (L+R)>>1;
		Node lc, rc;
		if(l < mid)
			lc = Get(2*id+0, L, mid, l, min(mid, r));
		if(r > mid)
			rc = Get(2*id+1, mid, R, max(l, mid), r);

		return Merge(lc, rc);
	}
};

int main() {
	IOS;
	
	cin >> n;
	for(int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		a[i] = -1;
		if(c == 'C')
			a[i] = 1;
	}

	SegTree s;
	s.initialize(1, 1, n+1);

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

		SegTree::Node g = s.Get(1, 1, n+1, l, r+1);
		cout << g.ans << "\n";
	}
}

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