Submission #854989

#	Time	Username	Problem	Language	Result	Execution time	Memory
854989		serifefedartar	Election (BOI18_election)	C++17	0 / 100	18 ms	131920 KiB

election

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20; 
const ll MAXN = 5e5 + 5;

int N, nxt[LOGN][MAXN], l, r, pref[MAXN];
int out[LOGN][MAXN], in[LOGN][MAXN];
map<int,int> occur;
vector<int> A;
string S;

struct Node {
	int sum, mn_suff;
	Node() : sum(0), mn_suff(0) { }
	Node(int s, int m) : sum(s), mn_suff(m) { }
} tmp, sg[4*MAXN];

Node merge(Node a, Node b) {
	Node new_node;
	new_node.sum = a.sum + b.sum;
	new_node.mn_suff = min(a.mn_suff + b.sum, b.mn_suff);
	return new_node;
}

void init(int k, int a, int b) {
	if (a == b) {
		sg[k] = Node(A[a], A[a]);
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = merge(sg[2*k], sg[2*k+1]);
}

Node query(int k, int a, int b, int q_l, int q_r) {
	if (q_r < a || q_l > b)
		return tmp;
	if (q_l <= a && b <= q_r)
		return sg[k];
	return merge(query(2*k, a, (a+b)/2, q_l, q_r), query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

int main() {
	fast
	cin >> N >> S;

	A = vector<int>(N+1);
	for (int i = 1; i <= N; i++) {
		A[i] = (S[i-1] == 'C' ? 1 : -1);
		pref[i] = pref[i-1] + A[i];
	}
	init(1, 1, N);

	int now = 0;
	nxt[0][N+1] = N+1;
	for (int i = N; i >= 1; i--) {
		now += A[i];
		if (A[i] == -1) {
			nxt[0][i] = i+1;
			out[0][i] = 1;
		} else if (occur[now]) {
			nxt[0][i] = occur[now];
			in[0][i] = max(0, -query(1, 1, N, i, nxt[0][i] - 1).mn_suff);
		} else {
			nxt[0][i] = N+1;
			in[0][i] = max(0, -query(1, 1, N, i, nxt[0][i] - 1).mn_suff);
		}
		occur[now] = i;
	}

	for (int i = 1; i < LOGN; i++) {
		for (int j = 1; j <= N+1; j++) {
			nxt[i][j] = nxt[i-1][nxt[i-1][j]];
			in[i][j] = max(in[i-1][j], in[i-1][nxt[i-1][j]]);
			out[i][j] = out[i-1][j] + out[i-1][nxt[i-1][j]];
		}
	}

	int Q;
	cin >> Q;
	while (Q--) {
		cin >> l >> r;
		int sum_in = 0, sum_out = 0;
		for (int i = LOGN - 1; i >= 0; i--) {
			if (nxt[i][l] <= r) {
				sum_out += out[i][l];
				sum_in = max(sum_in, in[i][l]);
				l = nxt[i][l];
			}
		}
		sum_in = max(0, sum_in - pref[N] + pref[l-1]);
		sum_in = max(sum_in, max(0, -query(1, 1, N, l, r).mn_suff));
		cout << sum_in + sum_out << "\n";
	}
}

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