oj.uz

Submission #67953

# Submission time Handle Problem Language Result Execution time Memory
67953 2018-08-15T15:29:02 Z aome Election (BOI18_election) C++17
100 / 100
 2387 ms 129464 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int INF = 1e9;

int n, m;
string s;
int sum[N];

struct Data {
	int sum, mx, cnt;

	Data() { sum = mx = cnt = 0; }
};

struct SegmentTree {
	struct Node {
		int sum, mx;
		vector<int> f;
	};

	Node T[N << 2];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		sum[l - 1] = 0;
		for (int j = l; j <= r; ++j) {
			sum[j] = sum[j - 1] + (s[j] == 'C' ? 1 : -1);
		}
		T[i].sum = sum[r];
		int cur = 0;
		vector<int> vec;
		for (int j = l - 1; j <= r; ++j) {
			if (sum[j] == cur) vec.push_back(j), --cur;
		}
		int sz = vec.size();
		T[i].f.assign(sz, 0);
		for (int j = 0; j < sz; ++j) {
			int mx = -INF;
			int tmp = j == sz - 1 ? r : vec[j + 1] - 1;
			for (int k = vec[j]; k <= tmp; ++k) {
				mx = max(mx, sum[k]);
			}
			T[i].f[j] = mx + 1;
		}
		for (int j = sz - 2; j >= 0; --j) T[i].f[j] = max(T[i].f[j], T[i].f[j + 1] + 1);
		int mx = 0;
		for (int j = 0; j < sz; ++j) {
			int tmp = j == sz - 1 ? r : vec[j + 1] - 1;
			for (int k = vec[j]; k <= tmp; ++k) mx = max(mx, sum[k]);
			T[i].f[j] = max(T[i].f[j], mx);
		}
		T[i].mx = mx;
		if (l == r) return;
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
	}

	void get(int i, int l, int r, int L, int R, Data &x) {
		if (l > R || L > r) return;
		if (L <= l && r <= R) {
			int tmp = x.sum + 1;
			int sz = T[i].f.size();
			if (sz <= tmp) {
				x.mx = max(x.mx, x.sum + T[i].mx), x.sum += T[i].sum; return;
			}
			x.mx = max(x.mx, x.sum + T[i].f[tmp]);
			x.sum += T[i].sum + sz - tmp;
			x.cnt += sz - tmp;
			return;
		}
		get(i << 1, l, mid, L, R, x);
		get(i << 1 | 1, mid + 1, r, L, R, x);
	}

	#undef mid
} IT;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> s, s = ' ' + s;
	IT.build(1, 1, n);
	cin >> m;
	while (m--) {
		int l, r; cin >> l >> r;
		Data tmp;
		IT.get(1, 1, n, l, r, tmp);
		cout << tmp.cnt + tmp.mx - tmp.sum << '\n';
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63096 KB Output is correct
2 Correct 76 ms 63312 KB Output is correct
3 Correct 77 ms 63312 KB Output is correct
4 Correct 73 ms 63412 KB Output is correct
5 Correct 63 ms 63512 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63096 KB Output is correct
2 Correct 76 ms 63312 KB Output is correct
3 Correct 77 ms 63312 KB Output is correct
4 Correct 73 ms 63412 KB Output is correct
5 Correct 63 ms 63512 KB Output is correct
6 Correct 321 ms 69484 KB Output is correct
7 Correct 299 ms 70248 KB Output is correct
8 Correct 317 ms 70552 KB Output is correct
9 Correct 264 ms 70552 KB Output is correct
10 Correct 263 ms 70552 KB Output is correct
11 Correct 306 ms 71388 KB Output is correct
12 Correct 288 ms 71936 KB Output is correct
13 Correct 325 ms 72760 KB Output is correct
14 Correct 306 ms 72760 KB Output is correct
15 Correct 274 ms 72760 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 63096 KB Output is correct
2 Correct 76 ms 63312 KB Output is correct
3 Correct 77 ms 63312 KB Output is correct
4 Correct 73 ms 63412 KB Output is correct
5 Correct 63 ms 63512 KB Output is correct
6 Correct 321 ms 69484 KB Output is correct
7 Correct 299 ms 70248 KB Output is correct
8 Correct 317 ms 70552 KB Output is correct
9 Correct 264 ms 70552 KB Output is correct
10 Correct 263 ms 70552 KB Output is correct
11 Correct 306 ms 71388 KB Output is correct
12 Correct 288 ms 71936 KB Output is correct
13 Correct 325 ms 72760 KB Output is correct
14 Correct 306 ms 72760 KB Output is correct
15 Correct 274 ms 72760 KB Output is correct
16 Correct 2087 ms 102124 KB Output is correct
17 Correct 2094 ms 102192 KB Output is correct
18 Correct 2256 ms 102192 KB Output is correct
19 Correct 1914 ms 102192 KB Output is correct
20 Correct 1839 ms 102192 KB Output is correct
21 Correct 2387 ms 108692 KB Output is correct
22 Correct 2012 ms 112044 KB Output is correct
23 Correct 2382 ms 126828 KB Output is correct
24 Correct 2033 ms 128228 KB Output is correct
25 Correct 2032 ms 129464 KB Output is correct