oj.uz

Submission #716480

# Submission time Handle Problem Language Result Execution time Memory
716480 2023-03-30T07:04:39 Z lukameladze Election (BOI18_election) C++14
100 / 100
 844 ms 50160 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
// #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 5e5 + 5;
int t,n,a[N],sf[N],pr[N],ans[N];
int tree[4 * N], lazy[4 * N];
vector <pii> v[N];
stack <int> st;
string s;
int merge(int a, int b) {
	return min(a, b);
}
void build(int node, int le, int ri) {
	if (le == ri) {
		tree[node] = sf[le];
//		lazy[node] = 0;
		return ;
	}
	int mid = (le + ri) / 2;
	build(2 * node, le, mid);
	build(2 * node + 1, mid + 1, ri);
	tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
void push(int node, int le, int ri) {
	if (!lazy[node]) return ;
	tree[node] += lazy[node];
	if (le != ri) {
    	lazy[2 * node] += lazy[node];
    	lazy[2 * node + 1] += lazy[node];
	}
	lazy[node] = 0;
}
void update(int node, int le, int ri, int start, int end, int val) {
	push(node,le,ri);
	if (le > end || ri < start) return ;
	if (le >= start && ri <= end) {
		lazy[node] = val;
		push(node,le,ri);
		return ;
	}
	int mid = (le + ri) / 2;
	update(2 * node,le,mid,start,end,val);
	update(2 * node + 1, mid + 1, ri, start, end,val);
	tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
int getans(int node, int le, int ri, int start, int end) {
	push(node,le,ri);
	if (le > end || ri < start) return 1e9;
	if (le >= start && ri <= end) {
		return tree[node];
	}
	int mid = (le + ri) / 2;
	return merge(getans(2 * node, le, mid,start,end), getans(2 * node + 1, mid + 1, ri, start, end));
}
int tree_f[N];
void upd(int idx, int val) {
//	cout<<"upd "<<idx<<" "<<val<<"\n";
	for (int i = idx; i < N; i+=i&(-i)) {
		tree_f[i] += val;
	}
}
int get(int idx) {
	int pas = 0;
	
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree_f[i];
	}
	return pas;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>s; s = "@" + s;
	for (int i = 1; i <= n; i++) {
		pr[i] = pr[i - 1] + (s[i] == 'C' ? 1 : -1);
	}
	for (int i = n; i >= 1; i--) {
		sf[i] = sf[i + 1] + (s[i] == 'C' ? 1 : -1);
	}
	build(1, 1, n);
	int q; cin>>q;
	for (int i = 1; i <= q; i++) {
		int l, r; cin>>l>>r;
		v[l].pb({r, i});
	}	
	for (int i = n; i >= 1; i--) {
		if (s[i] == 'T') {
			st.push(i); update(1, 1, n, 1, i, 1); upd(i, 1);
		} else {
			if (!st.empty()) {
				int x = st.top(); st.pop();
				update(1, 1, n, 1, x, -1); upd(x, -1);
			}
		}
		for (pii sth : v[i]) {
			int ri = sth.f; int id = sth.s;
			ans[id] = get(ri) + max(0, -(getans(1,1, n, i, ri) - sf[ri + 1] - get(n) + get(ri)));
		}
	}
	for (int i = 1; i <= q; i++) {
		cout<<ans[i]<<"\n";
	}
}

Compilation message

election.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main() {
      | ^~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 9 ms 12248 KB Output is correct
5 Correct 8 ms 12372 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 9 ms 12248 KB Output is correct
5 Correct 8 ms 12372 KB Output is correct
6 Correct 86 ms 17064 KB Output is correct
7 Correct 72 ms 16544 KB Output is correct
8 Correct 98 ms 16680 KB Output is correct
9 Correct 77 ms 16864 KB Output is correct
10 Correct 85 ms 16904 KB Output is correct
11 Correct 90 ms 17164 KB Output is correct
12 Correct 83 ms 17124 KB Output is correct
13 Correct 82 ms 17260 KB Output is correct
14 Correct 76 ms 16968 KB Output is correct
15 Correct 71 ms 16816 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 8 ms 12244 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct
4 Correct 9 ms 12248 KB Output is correct
5 Correct 8 ms 12372 KB Output is correct
6 Correct 86 ms 17064 KB Output is correct
7 Correct 72 ms 16544 KB Output is correct
8 Correct 98 ms 16680 KB Output is correct
9 Correct 77 ms 16864 KB Output is correct
10 Correct 85 ms 16904 KB Output is correct
11 Correct 90 ms 17164 KB Output is correct
12 Correct 83 ms 17124 KB Output is correct
13 Correct 82 ms 17260 KB Output is correct
14 Correct 76 ms 16968 KB Output is correct
15 Correct 71 ms 16816 KB Output is correct
16 Correct 844 ms 41112 KB Output is correct
17 Correct 662 ms 44744 KB Output is correct
18 Correct 829 ms 46132 KB Output is correct
19 Correct 625 ms 47444 KB Output is correct
20 Correct 766 ms 47884 KB Output is correct
21 Correct 736 ms 50160 KB Output is correct
22 Correct 747 ms 48728 KB Output is correct
23 Correct 725 ms 50020 KB Output is correct
24 Correct 686 ms 48200 KB Output is correct
25 Correct 662 ms 46412 KB Output is correct