oj.uz

Submission #364316

# Submission time Handle Problem Language Result Execution time Memory
364316 2021-02-08T23:08:17 Z cheissmart Election (BOI18_election) C++14
100 / 100
 533 ms 43008 KB 
#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 = 0, 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 << qry(l, r).ans << '\n';
	}

}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31596 KB Output is correct
2 Correct 26 ms 31724 KB Output is correct
3 Correct 22 ms 31724 KB Output is correct
4 Correct 22 ms 31724 KB Output is correct
5 Correct 26 ms 31724 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31596 KB Output is correct
2 Correct 26 ms 31724 KB Output is correct
3 Correct 22 ms 31724 KB Output is correct
4 Correct 22 ms 31724 KB Output is correct
5 Correct 26 ms 31724 KB Output is correct
6 Correct 69 ms 33028 KB Output is correct
7 Correct 67 ms 33132 KB Output is correct
8 Correct 67 ms 33024 KB Output is correct
9 Correct 60 ms 33004 KB Output is correct
10 Correct 85 ms 32940 KB Output is correct
11 Correct 72 ms 33132 KB Output is correct
12 Correct 69 ms 33132 KB Output is correct
13 Correct 74 ms 33132 KB Output is correct
14 Correct 83 ms 33132 KB Output is correct
15 Correct 71 ms 33004 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31596 KB Output is correct
2 Correct 26 ms 31724 KB Output is correct
3 Correct 22 ms 31724 KB Output is correct
4 Correct 22 ms 31724 KB Output is correct
5 Correct 26 ms 31724 KB Output is correct
6 Correct 69 ms 33028 KB Output is correct
7 Correct 67 ms 33132 KB Output is correct
8 Correct 67 ms 33024 KB Output is correct
9 Correct 60 ms 33004 KB Output is correct
10 Correct 85 ms 32940 KB Output is correct
11 Correct 72 ms 33132 KB Output is correct
12 Correct 69 ms 33132 KB Output is correct
13 Correct 74 ms 33132 KB Output is correct
14 Correct 83 ms 33132 KB Output is correct
15 Correct 71 ms 33004 KB Output is correct
16 Correct 533 ms 42052 KB Output is correct
17 Correct 496 ms 41600 KB Output is correct
18 Correct 462 ms 41856 KB Output is correct
19 Correct 384 ms 41344 KB Output is correct
20 Correct 533 ms 41088 KB Output is correct
21 Correct 502 ms 42752 KB Output is correct
22 Correct 512 ms 42752 KB Output is correct
23 Correct 529 ms 43008 KB Output is correct
24 Correct 527 ms 42616 KB Output is correct
25 Correct 509 ms 42320 KB Output is correct