Submission #488004

#	Time	Username	Problem	Language	Result	Execution time	Memory
488004		grt	Election (BOI18_election)	C++17	100 / 100	760 ms	96392 KiB

election

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 500 * 1000 + 10;
int n, q;
string s;
int val[nax], last[2 * nax], nxt[nax][20], f[nax][20];
int T[(1 << 20)], R;

void upd(int a, int x) {
	a += R;
	T[a] = x;
	while(a > 1) {
		a /= 2;
		T[a] = max(T[2*a],T[2*a+1]);
	}
}

int qr(int a, int b) {
	a += R; b += R;
	int w = max(T[a], T[b]);
	while(a/2!=b/2) {
		if(a%2==0)w=max(w,T[a+1]);
		if(b%2==1)w=max(w,T[b-1]);
		a/=2;
		b/=2;
	}
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	R = 1;
	while(R <= n) R *= 2;
	for(int i = 1; i <= n; ++i) {
		val[i] = val[i - 1] + (s[i - 1] == 'C' ? 1 : -1);
		upd(i, val[i]);
	}
	for(int i = n; i >= 0; --i) {
		nxt[i][0] = last[val[i] - 1 + n + 1];
		if(nxt[i][0] == 0) nxt[i][0] = n + 1;
		f[i][0] = qr(i, nxt[i][0] - 1);
		last[val[i] + n + 1] = i;
	}
	nxt[n + 1][0] = n + 1;
	for(int step = 1; step < 20; ++step) {
		for(int i = 0; i <= n; ++i) {
			nxt[i][step] = nxt[nxt[i][step - 1]][step - 1];
			f[i][step] = max(f[i][step - 1], f[nxt[i][step - 1]][step - 1] + (1 << (step - 1)));
		}
		nxt[n + 1][step] = n + 1;
	}
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		l--;
		int mx = val[l], total = 0;
		for(int i = 19; i >= 0; --i) {
			if(nxt[l][i] <= r) {
				mx = max(mx, f[l][i] + total);
				total += (1 << i);
				l = nxt[l][i];
			}
		}
		mx = max(mx, qr(l, r) + total);
		int ans = total + max(0, mx - (val[r] + total));
		cout << ans << "\n";
	}
	
	
}

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