Submission #364317

#	Time	Username	Problem	Language	Result	Execution time	Memory
364317		cheissmart	Election (BOI18_election)	C++14	100 / 100	575 ms	35328 KiB

election

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 500005;

int n;
string s;

struct node {
	int ans, l, r, s;
	node(char c = 'C') {
		if(c == 'C') l = r = 0, ans = -1, s = -1;
		else ans = l = r = s = 1;
	}
	node operator + (node t) {
		node res;
		res.s = s + t.s;
		res.l = max(l, s + t.l);
		res.r = max(r + t.s, t.r);
		res.ans = max({l + t.r, s + t.ans, t.s + ans});
		return res;
	}
} t[N * 4];

void build(int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = node(s[tl]);
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm);
	build(v * 2 + 1, tm, tr);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

node qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r) return t[v];
	int tm = (tl + tr) / 2;
	if(r <= tm) return qry(l, r, v * 2, tl, tm);
	else if(l >= tm) return qry(l, r, v * 2 + 1, tm, tr);
	else return qry(l, r, v * 2, tl, tm) + qry(l, r, v * 2 + 1, tm, tr);
}

signed main()
{
	IO_OP;

	cin >> n >> s;

	build();

	int q;
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		l--;
		cout << max(qry(l, r).ans, 0) << '\n';
	}

}

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