Submission #1266180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266180		g4yuhg	Election (BOI18_election)	C++20	100 / 100	295 ms	20396 KiB

election

//Huyduocdithitp
#include <bits/stdc++.h>
typedef int ll;
#define pii pair<ll, ll> 
#define MP make_pair
#define fi first
#define se second
#define TASK "connect"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 500005
#define LOG 18
#define endl '\n'
using namespace std;

ll n, q;
string s;

struct Node {
	ll L, R, S, A;
} st[4 * N];

Node cb(Node u, Node v) {
	Node w;
	w.L = max(u.L, u.S + v.L);
	w.R = max(v.R, v.S + u.R);
	w.S = u.S + v.S;
	w.A = max({u.A + v.S, u.S + v.A, u.L + v.R});
	return w;
}

void build(ll id, ll l, ll r) {
	if (l == r) {
		if (s[l] == 'C') {
			st[id] = {0, 0, -1, 0};
		}
		else {
			st[id] = {1, 1, 1, 1};
		}
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = cb(st[id * 2], st[id * 2 + 1]);
}

Node get(ll id, ll l, ll r, ll L, ll R) {
	if (l > R || r < L) return {0, 0, 0, 0};
	if (L <= l && r <= R) return st[id];
	ll mid = (l + r) / 2;
	return cb(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R));
}

signed main(void) {
	faster;
	
	cin >> n;
	cin >> s;
	cin >> q;
	s = '*' + s;
	build(1, 1, n);
	for (int i = 1; i <= q; i ++) {
		ll l, r;
		cin >> l >> r;
		cout << get(1, 1, n, l, r).A << endl;
	}
	
	
	return 0;
}

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