oj.uz

Submission #1096550

# Submission time Handle Problem Language Result Execution time Memory
1096550 2024-10-04T18:10:22 Z kamrad Election (BOI18_election) C++17
100 / 100
 356 ms 44196 KB 
#include <bits/stdc++.h>

using namespace std;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define IOS      ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F        first
#define S        second
#define sz(x)    int(x.size())
#define all(x)   x.begin(), x.end()
#define pb       push_back

const int Inf    = 2e9 + 10;
const int Mod    = 1e9 + 7;
const int LG     = 25;
const int SQ     = 400;
const int Alpha  = 27;
const int maxN   = 5e5 + 10;

int n, q;
int a[maxN];

struct SegTree {
	struct Node {
		int sum;
		int mnLR;
		int mnRL;
		int ans;
		Node() {
			sum = mnLR = mnRL = ans = 0;
		}
	} t[maxN<<2];
	
	Node Merge(Node lc, Node rc) {
		Node ret;
		ret.sum = lc.sum + rc.sum;
		ret.mnLR = min(lc.mnLR, lc.sum + rc.mnLR);
		ret.mnRL = min(rc.mnRL, rc.sum + lc.mnRL);
		ret.ans = max( -(lc.mnLR + rc.mnRL), max(lc.ans - rc.sum, rc.ans - lc.sum));
		return ret;
	}

	void initialize(int id, int L, int R) {
		if(L+1 == R) {
			t[id].sum = a[L];
			t[id].mnLR = min(0, a[L]);
			t[id].mnRL = min(0, a[L]);
			t[id].ans = abs(min(0, a[L]));
			return;
		}

		int mid = (L+R)>>1;
		initialize(2*id+0, L, mid);
		initialize(2*id+1, mid, R);
		
		t[id] = Merge(t[2*id+0], t[2*id+1]);
	}

	Node Get(int id, int L, int R, int l, int r) {
		if(L == l and R == r)
			return t[id];

		int mid = (L+R)>>1;
		Node lc, rc;
		if(l < mid)
			lc = Get(2*id+0, L, mid, l, min(mid, r));
		if(r > mid)
			rc = Get(2*id+1, mid, R, max(l, mid), r);

		return Merge(lc, rc);
	}
};

int main() {
	IOS;
	
	cin >> n;
	for(int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		a[i] = -1;
		if(c == 'C')
			a[i] = 1;
	}

	SegTree s;
	s.initialize(1, 1, n+1);

	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;

		SegTree::Node g = s.Get(1, 1, n+1, l, r+1);
		cout << g.ans << "\n";
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31684 KB Output is correct
2 Correct 18 ms 31576 KB Output is correct
3 Correct 17 ms 31576 KB Output is correct
4 Correct 19 ms 31580 KB Output is correct
5 Correct 18 ms 31784 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31684 KB Output is correct
2 Correct 18 ms 31576 KB Output is correct
3 Correct 17 ms 31576 KB Output is correct
4 Correct 19 ms 31580 KB Output is correct
5 Correct 18 ms 31784 KB Output is correct
6 Correct 52 ms 33104 KB Output is correct
7 Correct 47 ms 33032 KB Output is correct
8 Correct 48 ms 33004 KB Output is correct
9 Correct 46 ms 33048 KB Output is correct
10 Correct 49 ms 33104 KB Output is correct
11 Correct 51 ms 33104 KB Output is correct
12 Correct 50 ms 33108 KB Output is correct
13 Correct 50 ms 33108 KB Output is correct
14 Correct 49 ms 33104 KB Output is correct
15 Correct 49 ms 33092 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31684 KB Output is correct
2 Correct 18 ms 31576 KB Output is correct
3 Correct 17 ms 31576 KB Output is correct
4 Correct 19 ms 31580 KB Output is correct
5 Correct 18 ms 31784 KB Output is correct
6 Correct 52 ms 33104 KB Output is correct
7 Correct 47 ms 33032 KB Output is correct
8 Correct 48 ms 33004 KB Output is correct
9 Correct 46 ms 33048 KB Output is correct
10 Correct 49 ms 33104 KB Output is correct
11 Correct 51 ms 33104 KB Output is correct
12 Correct 50 ms 33108 KB Output is correct
13 Correct 50 ms 33108 KB Output is correct
14 Correct 49 ms 33104 KB Output is correct
15 Correct 49 ms 33092 KB Output is correct
16 Correct 356 ms 43092 KB Output is correct
17 Correct 295 ms 42720 KB Output is correct
18 Correct 302 ms 43092 KB Output is correct
19 Correct 268 ms 42568 KB Output is correct
20 Correct 334 ms 42324 KB Output is correct
21 Correct 335 ms 44116 KB Output is correct
22 Correct 311 ms 43860 KB Output is correct
23 Correct 326 ms 44196 KB Output is correct
24 Correct 306 ms 43972 KB Output is correct
25 Correct 336 ms 43256 KB Output is correct