oj.uz

Submission #365327

# Submission time Handle Problem Language Result Execution time Memory
365327 2021-02-11T13:07:27 Z kostia244 Election (BOI18_election) C++17
100 / 100
 1365 ms 59676 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
 
template<typename F>
void multitest(F func) {
	int t;
	cin >> t;
	while(t--) func();
}
void report(int ok) {
	cout << (ok?"YES":"NO") << '\n';
}
struct segtree {
	struct node {
		int mn, lazy;
		node() : mn(0), lazy(0) {}
		void apply(int x) {
			mn += x, lazy += x;
		}
		void push(node &l, node &r) {
			l.apply(lazy), r.apply(lazy), lazy = 0;
		}
		void build(node &l, node &r) {
			mn = min(l.mn, r.mn);
			assert(!lazy);
		}
	};
	vector<node> st;
	int n;
	segtree(int n) : st(4*n), n(n) {}
	void update(int v, int l, int r, int ql, int qr, int add) {
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr) {
			st[v].apply(add);
			return;
		}
		st[v].push(st[2*v], st[2*v+1]);
		int mid = (l+r)/2;
		update(2*v, l, mid, ql, qr, add);
		update(2*v+1, mid+1, r, ql, qr, add);
		st[v].build(st[2*v], st[2*v+1]);
	}
	void update(int l, int r, int add) { return update(1, 1, n, l, r, add); }
	int query(int v, int l, int r, int ql, int qr) {
		if(qr < l || r < ql) return 1<<30;
		if(ql <= l && r <= qr) return st[v].mn;
		st[v].push(st[2*v], st[2*v+1]);
		int mid = (l+r)/2;
		return min(query(2*v, l, mid, ql, qr), query(2*v+1, mid+1, r, ql, qr));
	}
	int query(int l, int r) { return query(1, 1, n, l, r); }
};
int n, q, a[1<<20], pref[1<<20], ans[1<<20];
vector<array<int, 2>> todo[1<<20];
segtree st(0);
int main() {
	cin.tie(0)->sync_with_stdio(0);
	//multitest([&](){});
	cin >> n;
	st = segtree(n);
	char c;
	for(int i = 1; i <= n; i++) cin >> c, a[i] = c=='C'?1:-1, pref[i] = pref[i-1]+a[i];
	cin >> q;
	for(int l, r, i = 0; i < q; i++) {
		cin >> l >> r;
		todo[r].push_back({l, i});
	}
	vector<int> bad;
	for(int i = 1; i <= n; i++) {
		st.update(i, n, a[i]);
		if(a[i] == 1 && bad.size()) {
			st.update(bad.back(), n, -1);
			bad.pop_back();
		}
		if(a[i] == -1) {
			bad.push_back(i);
			st.update(i, n, 1);
		}
		//for(auto i : bad) cout << i << " "; cout << endl;
		for(auto [l, id] : todo[i]) {
			int mn = st.query(l, i) - (l>1?st.query(l-1, l-1):0);
			ans[id] = bad.end() - lower_bound(all(bad), l);
			//cout << l << " ff " << ans[id] << endl;
			ans[id] += max(0, -mn);
		}
	}
	for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25068 KB Output is correct
2 Correct 20 ms 25088 KB Output is correct
3 Correct 20 ms 25068 KB Output is correct
4 Correct 21 ms 25216 KB Output is correct
5 Correct 22 ms 25068 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25068 KB Output is correct
2 Correct 20 ms 25088 KB Output is correct
3 Correct 20 ms 25068 KB Output is correct
4 Correct 21 ms 25216 KB Output is correct
5 Correct 22 ms 25068 KB Output is correct
6 Correct 146 ms 29632 KB Output is correct
7 Correct 137 ms 29292 KB Output is correct
8 Correct 163 ms 29292 KB Output is correct
9 Correct 141 ms 29548 KB Output is correct
10 Correct 134 ms 29548 KB Output is correct
11 Correct 152 ms 29804 KB Output is correct
12 Correct 175 ms 29676 KB Output is correct
13 Correct 149 ms 29932 KB Output is correct
14 Correct 138 ms 29676 KB Output is correct
15 Correct 133 ms 29548 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25068 KB Output is correct
2 Correct 20 ms 25088 KB Output is correct
3 Correct 20 ms 25068 KB Output is correct
4 Correct 21 ms 25216 KB Output is correct
5 Correct 22 ms 25068 KB Output is correct
6 Correct 146 ms 29632 KB Output is correct
7 Correct 137 ms 29292 KB Output is correct
8 Correct 163 ms 29292 KB Output is correct
9 Correct 141 ms 29548 KB Output is correct
10 Correct 134 ms 29548 KB Output is correct
11 Correct 152 ms 29804 KB Output is correct
12 Correct 175 ms 29676 KB Output is correct
13 Correct 149 ms 29932 KB Output is correct
14 Correct 138 ms 29676 KB Output is correct
15 Correct 133 ms 29548 KB Output is correct
16 Correct 1271 ms 57976 KB Output is correct
17 Correct 1041 ms 55660 KB Output is correct
18 Correct 1153 ms 56428 KB Output is correct
19 Correct 1093 ms 57844 KB Output is correct
20 Correct 1190 ms 57212 KB Output is correct
21 Correct 1365 ms 59348 KB Output is correct
22 Correct 1238 ms 58892 KB Output is correct
23 Correct 1291 ms 59676 KB Output is correct
24 Correct 1231 ms 58852 KB Output is correct
25 Correct 1148 ms 58068 KB Output is correct