oj.uz

Submission #648625

# Submission time Handle Problem Language Result Execution time Memory
648625 2022-10-07T08:13:19 Z ymm Election (BOI18_election) C++17
100 / 100
 471 ms 27748 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 500'010;
struct node {
	int mnl, mnr, mns;
} seg[N*4];

string s;
int pre[N], suf[N];
int n;

node merge(node x, node y)
{
	node ans;
	ans.mnl = min(x.mnl, y.mnl);
	ans.mnr = min(x.mnr, y.mnr);
	ans.mns = min({x.mns, y.mns, x.mnl + y.mnr});
	return ans;
}

void build(int i, int b, int e)
{
	if (e-b == 1) {
		seg[i].mnl = pre[b];
		seg[i].mnr = suf[b];
		seg[i].mns = seg[i].mnl + seg[i].mnr;
		return;
	}
	build(2*i+1, b, (b+e)/2);
	build(2*i+2, (b+e)/2, e);
	seg[i] = merge(seg[2*i+1], seg[2*i+2]);
}

node get(int l, int r, int i, int b, int e)
{
	if (l <= b && e <= r)
		return seg[i];
	int mid = (b+e)/2;
	if (l < mid && mid < r) {
		return merge(get(l, r, 2*i+1, b, mid),
		             get(l, r, 2*i+2, mid, e));
	} else if (l < mid) {
		return get(l, r, 2*i+1, b, mid);
	} else if (mid < r) {
		return get(l, r, 2*i+2, mid, e);
	} else {
		for (;;)
			cerr << "666\n";
		*(int *)666 = 666;
		return node{666, 666, 666};
		// >:)
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> n;
	cin >> s;
	Loop (i,0,n)
		pre[i+1] = pre[i] + (s[i] == 'C'? 1: -1);
	LoopR (i,0,n)
		suf[i] = suf[i+1] + (s[i] == 'C'? 1: -1);
	build(0, 0, n+1);
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		--l;
		auto ans = get(l, r+1, 0, 0, n+1);
		cout << -(ans.mns - pre[l] - suf[r]) << '\n';
	}
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 47 ms 5316 KB Output is correct
7 Correct 47 ms 5208 KB Output is correct
8 Correct 50 ms 5268 KB Output is correct
9 Correct 49 ms 5276 KB Output is correct
10 Correct 46 ms 5220 KB Output is correct
11 Correct 42 ms 5324 KB Output is correct
12 Correct 43 ms 5384 KB Output is correct
13 Correct 44 ms 5348 KB Output is correct
14 Correct 46 ms 5396 KB Output is correct
15 Correct 50 ms 5300 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 47 ms 5316 KB Output is correct
7 Correct 47 ms 5208 KB Output is correct
8 Correct 50 ms 5268 KB Output is correct
9 Correct 49 ms 5276 KB Output is correct
10 Correct 46 ms 5220 KB Output is correct
11 Correct 42 ms 5324 KB Output is correct
12 Correct 43 ms 5384 KB Output is correct
13 Correct 44 ms 5348 KB Output is correct
14 Correct 46 ms 5396 KB Output is correct
15 Correct 50 ms 5300 KB Output is correct
16 Correct 467 ms 26712 KB Output is correct
17 Correct 407 ms 26472 KB Output is correct
18 Correct 407 ms 26576 KB Output is correct
19 Correct 331 ms 26136 KB Output is correct
20 Correct 471 ms 25884 KB Output is correct
21 Correct 466 ms 27620 KB Output is correct
22 Correct 460 ms 27504 KB Output is correct
23 Correct 470 ms 27748 KB Output is correct
24 Correct 449 ms 27476 KB Output is correct
25 Correct 464 ms 26976 KB Output is correct