oj.uz

Submission #488004

# Submission time Handle Problem Language Result Execution time Memory
488004 2021-11-17T11:51:42 Z grt Election (BOI18_election) C++17
100 / 100
 760 ms 96392 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 500 * 1000 + 10;
int n, q;
string s;
int val[nax], last[2 * nax], nxt[nax][20], f[nax][20];
int T[(1 << 20)], R;

void upd(int a, int x) {
	a += R;
	T[a] = x;
	while(a > 1) {
		a /= 2;
		T[a] = max(T[2*a],T[2*a+1]);
	}
}

int qr(int a, int b) {
	a += R; b += R;
	int w = max(T[a], T[b]);
	while(a/2!=b/2) {
		if(a%2==0)w=max(w,T[a+1]);
		if(b%2==1)w=max(w,T[b-1]);
		a/=2;
		b/=2;
	}
	return w;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s;
	R = 1;
	while(R <= n) R *= 2;
	for(int i = 1; i <= n; ++i) {
		val[i] = val[i - 1] + (s[i - 1] == 'C' ? 1 : -1);
		upd(i, val[i]);
	}
	for(int i = n; i >= 0; --i) {
		nxt[i][0] = last[val[i] - 1 + n + 1];
		if(nxt[i][0] == 0) nxt[i][0] = n + 1;
		f[i][0] = qr(i, nxt[i][0] - 1);
		last[val[i] + n + 1] = i;
	}
	nxt[n + 1][0] = n + 1;
	for(int step = 1; step < 20; ++step) {
		for(int i = 0; i <= n; ++i) {
			nxt[i][step] = nxt[nxt[i][step - 1]][step - 1];
			f[i][step] = max(f[i][step - 1], f[nxt[i][step - 1]][step - 1] + (1 << (step - 1)));
		}
		nxt[n + 1][step] = n + 1;
	}
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		l--;
		int mx = val[l], total = 0;
		for(int i = 19; i >= 0; --i) {
			if(nxt[l][i] <= r) {
				mx = max(mx, f[l][i] + total);
				total += (1 << i);
				l = nxt[l][i];
			}
		}
		mx = max(mx, qr(l, r) + total);
		int ans = total + max(0, mx - (val[r] + total));
		cout << ans << "\n";
	}
	
	
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 61 ms 13516 KB Output is correct
7 Correct 59 ms 13476 KB Output is correct
8 Correct 53 ms 13424 KB Output is correct
9 Correct 55 ms 13408 KB Output is correct
10 Correct 59 ms 13412 KB Output is correct
11 Correct 64 ms 13656 KB Output is correct
12 Correct 64 ms 13624 KB Output is correct
13 Correct 70 ms 13708 KB Output is correct
14 Correct 61 ms 13644 KB Output is correct
15 Correct 60 ms 13620 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 2 ms 848 KB Output is correct
3 Correct 1 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 720 KB Output is correct
6 Correct 61 ms 13516 KB Output is correct
7 Correct 59 ms 13476 KB Output is correct
8 Correct 53 ms 13424 KB Output is correct
9 Correct 55 ms 13408 KB Output is correct
10 Correct 59 ms 13412 KB Output is correct
11 Correct 64 ms 13656 KB Output is correct
12 Correct 64 ms 13624 KB Output is correct
13 Correct 70 ms 13708 KB Output is correct
14 Correct 61 ms 13644 KB Output is correct
15 Correct 60 ms 13620 KB Output is correct
16 Correct 538 ms 94684 KB Output is correct
17 Correct 491 ms 94228 KB Output is correct
18 Correct 496 ms 94756 KB Output is correct
19 Correct 517 ms 94056 KB Output is correct
20 Correct 523 ms 94168 KB Output is correct
21 Correct 760 ms 96008 KB Output is correct
22 Correct 642 ms 95764 KB Output is correct
23 Correct 730 ms 96392 KB Output is correct
24 Correct 673 ms 95936 KB Output is correct
25 Correct 596 ms 95928 KB Output is correct