Submission #1096528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096528		kamrad	Election (BOI18_election)	C++17	0 / 100	16 ms	23896 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;
		Node() {
			sum = 0;
		}
	} t[maxN<<2];

	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]);
			return;
		}

		int mid = (L+R)>>1;
		initialize(2*id+0, L, mid);
		initialize(2*id+1, mid, R);

		t[id].sum = t[2*id+0].sum + t[2*id+1].sum;
		t[id].mnLR = min(0, min(t[2*id+0].mnLR, t[2*id+0].sum + t[2*id+1].mnLR));
		t[id].mnRL = min(0, min(t[2*id+1].mnRL, t[2*id+1].sum + t[2*id+0].mnRL));
	}

	void Get(int id, int L, int R, int l, int r, vector <int> &g) {
		if(L == l and R == r) {
			g.pb(id);
			return;
		}

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

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;

		vector <int> g;
		g.clear();
		s.Get(1, 1, n+1, l, r+1, g);

		int mn1 = Inf;
		int mn2 = Inf;

		int CurSum = 0;
		for(int i = 0; i < sz(g); i++) {
			int tmp = s.t[g[i]].mnLR;
			tmp += CurSum;
			CurSum += s.t[g[i]].sum;

			mn1 = min(mn1, tmp);
		}

		CurSum = 0;
		for(int i = sz(g)-1; i >= 0; i--) {
			int tmp = s.t[g[i]].mnRL;
			tmp += CurSum;
			CurSum += s.t[g[i]].sum;

			mn2 = min(mn2, tmp);
		}

		cout << abs(min(0, min(mn1, mn2))) << "\n" << flush;
	}
}

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