oj.uz

Submission #716479

# Submission time Handle Problem Language Result Execution time Memory
716479 2023-03-30T07:04:10 Z lukameladze Election (BOI18_election) C++14
82 / 100
 235 ms 71460 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 = 3e5 + 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 6 ms 7508 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 6 ms 7508 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7524 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7508 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 6 ms 7508 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7524 KB Output is correct
6 Correct 79 ms 13272 KB Output is correct
7 Correct 73 ms 12732 KB Output is correct
8 Correct 98 ms 12888 KB Output is correct
9 Correct 84 ms 13140 KB Output is correct
10 Correct 73 ms 13124 KB Output is correct
11 Correct 72 ms 13468 KB Output is correct
12 Correct 81 ms 13324 KB Output is correct
13 Correct 77 ms 13512 KB Output is correct
14 Correct 81 ms 13384 KB Output is correct
15 Correct 68 ms 13032 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7508 KB Output is correct
2 Correct 5 ms 7508 KB Output is correct
3 Correct 6 ms 7508 KB Output is correct
4 Correct 5 ms 7508 KB Output is correct
5 Correct 5 ms 7524 KB Output is correct
6 Correct 79 ms 13272 KB Output is correct
7 Correct 73 ms 12732 KB Output is correct
8 Correct 98 ms 12888 KB Output is correct
9 Correct 84 ms 13140 KB Output is correct
10 Correct 73 ms 13124 KB Output is correct
11 Correct 72 ms 13468 KB Output is correct
12 Correct 81 ms 13324 KB Output is correct
13 Correct 77 ms 13512 KB Output is correct
14 Correct 81 ms 13384 KB Output is correct
15 Correct 68 ms 13032 KB Output is correct
16 Runtime error 235 ms 71460 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -