oj.uz

Submission #854990

# Submission time Handle Problem Language Result Execution time Memory
854990 2023-09-29T16:55:59 Z serifefedartar Election (BOI18_election) C++17
100 / 100
 1041 ms 159716 KB 
#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[r] + 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
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 131908 KB Output is correct
2 Correct 15 ms 131900 KB Output is correct
3 Correct 16 ms 131944 KB Output is correct
4 Correct 15 ms 131932 KB Output is correct
5 Correct 16 ms 131932 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 131908 KB Output is correct
2 Correct 15 ms 131900 KB Output is correct
3 Correct 16 ms 131944 KB Output is correct
4 Correct 15 ms 131932 KB Output is correct
5 Correct 16 ms 131932 KB Output is correct
6 Correct 65 ms 133712 KB Output is correct
7 Correct 66 ms 133636 KB Output is correct
8 Correct 64 ms 133768 KB Output is correct
9 Correct 64 ms 133752 KB Output is correct
10 Correct 76 ms 134228 KB Output is correct
11 Correct 69 ms 134692 KB Output is correct
12 Correct 80 ms 134028 KB Output is correct
13 Correct 75 ms 134992 KB Output is correct
14 Correct 73 ms 134224 KB Output is correct
15 Correct 86 ms 135056 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 131908 KB Output is correct
2 Correct 15 ms 131900 KB Output is correct
3 Correct 16 ms 131944 KB Output is correct
4 Correct 15 ms 131932 KB Output is correct
5 Correct 16 ms 131932 KB Output is correct
6 Correct 65 ms 133712 KB Output is correct
7 Correct 66 ms 133636 KB Output is correct
8 Correct 64 ms 133768 KB Output is correct
9 Correct 64 ms 133752 KB Output is correct
10 Correct 76 ms 134228 KB Output is correct
11 Correct 69 ms 134692 KB Output is correct
12 Correct 80 ms 134028 KB Output is correct
13 Correct 75 ms 134992 KB Output is correct
14 Correct 73 ms 134224 KB Output is correct
15 Correct 86 ms 135056 KB Output is correct
16 Correct 594 ms 147600 KB Output is correct
17 Correct 403 ms 147096 KB Output is correct
18 Correct 459 ms 147428 KB Output is correct
19 Correct 458 ms 146936 KB Output is correct
20 Correct 681 ms 151248 KB Output is correct
21 Correct 1041 ms 153164 KB Output is correct
22 Correct 651 ms 151812 KB Output is correct
23 Correct 769 ms 155444 KB Output is correct
24 Correct 705 ms 154004 KB Output is correct
25 Correct 677 ms 159716 KB Output is correct