oj.uz

Submission #67946

# Submission time Handle Problem Language Result Execution time Memory
67946 2018-08-15T15:08:34 Z aome Election (BOI18_election) C++17
0 / 100
 105 ms 110264 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, T[i].g.back()), x.sum += T[i].s; return;
			}
			x.mx = max(x.mx, 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
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 110264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 110264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 110264 KB Output isn't correct
2 Halted 0 ms 0 KB -