oj.uz

Submission #67950

# Submission time Handle Problem Language Result Execution time Memory
67950 2018-08-15T15:21:30 Z aome Election (BOI18_election) C++17
82 / 100
 2955 ms 263168 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 s;
		vector<int> f, g;
	};

	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].s = 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;
		}
		cur = 0;
		int sz = vec.size();
		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.push_back(mx + 1);
			cur = max(cur, mx);
			T[i].g.push_back(cur);
		}
		for (int j = sz - 2; j >= 0; --j) T[i].f[j] = max(T[i].f[j], T[i].f[j + 1] + 1);
		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;
			if (T[i].f.size() <= tmp) {
				x.mx = max(x.mx, x.sum + T[i].g.back()), x.sum += T[i].s; return;
			}
			x.mx = max(x.mx, x.sum + max(T[i].g[tmp], T[i].f[tmp]));
			x.sum += T[i].s + T[i].f.size() - tmp;
			x.cnt += T[i].f.size() - 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';
	}
}

Compilation message

election.cpp: In member function 'void SegmentTree::get(int, int, int, int, int, Data&)':
election.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (T[i].f.size() <= tmp) {
        ~~~~~~~~~~~~~~^~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 110200 KB Output is correct
2 Correct 111 ms 110372 KB Output is correct
3 Correct 104 ms 110372 KB Output is correct
4 Correct 105 ms 110460 KB Output is correct
5 Correct 102 ms 110460 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 110200 KB Output is correct
2 Correct 111 ms 110372 KB Output is correct
3 Correct 104 ms 110372 KB Output is correct
4 Correct 105 ms 110460 KB Output is correct
5 Correct 102 ms 110460 KB Output is correct
6 Correct 456 ms 120920 KB Output is correct
7 Correct 420 ms 121688 KB Output is correct
8 Correct 411 ms 122520 KB Output is correct
9 Correct 372 ms 123436 KB Output is correct
10 Correct 406 ms 124128 KB Output is correct
11 Correct 396 ms 127252 KB Output is correct
12 Correct 478 ms 130676 KB Output is correct
13 Correct 453 ms 133944 KB Output is correct
14 Correct 382 ms 133944 KB Output is correct
15 Correct 378 ms 133944 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 110200 KB Output is correct
2 Correct 111 ms 110372 KB Output is correct
3 Correct 104 ms 110372 KB Output is correct
4 Correct 105 ms 110460 KB Output is correct
5 Correct 102 ms 110460 KB Output is correct
6 Correct 456 ms 120920 KB Output is correct
7 Correct 420 ms 121688 KB Output is correct
8 Correct 411 ms 122520 KB Output is correct
9 Correct 372 ms 123436 KB Output is correct
10 Correct 406 ms 124128 KB Output is correct
11 Correct 396 ms 127252 KB Output is correct
12 Correct 478 ms 130676 KB Output is correct
13 Correct 453 ms 133944 KB Output is correct
14 Correct 382 ms 133944 KB Output is correct
15 Correct 378 ms 133944 KB Output is correct
16 Correct 2441 ms 197360 KB Output is correct
17 Correct 2508 ms 204448 KB Output is correct
18 Correct 2365 ms 211948 KB Output is correct
19 Correct 2206 ms 219076 KB Output is correct
20 Correct 2498 ms 223816 KB Output is correct
21 Correct 2955 ms 250452 KB Output is correct
22 Runtime error 2946 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
23 Halted 0 ms 0 KB -