oj.uz

Submission #578381

# Submission time Handle Problem Language Result Execution time Memory
578381 2022-06-16T13:33:47 Z AlperenT Election (BOI18_election) C++17
100 / 100
 1874 ms 50032 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5, INF = 1e9 + 5;

int n, q, l, r, ans[N], mn;

char arr[N];

vector<pair<int, int>> query[N];

stack<int> stk;

// bool vis[N];

struct Fenwick{
	int tree[N];

	int query(int pos){
		int sum = 0;
		for(int i = pos; i > 0; i -= i & -i) sum += tree[i];
		return sum;
	}

	void update(int pos, int val){
		for(int i = pos; i < N; i += i & -i) tree[i] += val;
	}

	void range_update(int l, int r, int val){
		if(l <= r){
			update(l, val);
			update(r + 1, -val);
		}
	}
};

Fenwick fw;

struct SegTree{
	int tree[N * 4], lazy[N * 4];

	int merge(int a, int b){
		return max(a, b);
	}

	void push(int v){
		if(lazy[v]){
			tree[v] += lazy[v];

			if(v * 2 < N * 4) lazy[v * 2] += lazy[v], lazy[v * 2 + 1] += lazy[v];

			lazy[v] = 0;
		}
	}

	void update(int l, int r, int val, int v = 1, int tl = 1, int tr = n){
		if(l > r) return;
		else if(tl == l && tr == r) lazy[v] += val;
		else{
			push(v);

			int tm = tl + (tr - tl) / 2;

			update(l, min(tm, r), val, v * 2, tl, tm);
			update(max(tm + 1, l), r, val, v * 2 + 1, tm + 1, tr);

			push(v * 2), push(v * 2 + 1);

			tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
		}
	}

	int query(int l, int r, int v = 1, int tl = 1, int tr = n){
		if(l > r) return -INF;

		push(v);

		if(l == tl && r == tr) return tree[v];
		else{
			int tm = tl + (tr - tl) / 2;

			return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
		}
	}
};

SegTree sgt;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	
	cin >> n;

	for(int i = 1; i <= n; i++) cin >> arr[i];

	cin >> q;

	for(int i = 1; i <= q; i++){
		cin >> l >> r;

		query[l].push_back({r, i});
	}

	mn = INF;

	for(int i = n; i >= 1; i--){
		if(arr[i] == 'C'){
			sgt.update(i, n, 1);

			if(!stk.empty()){
				sgt.update(stk.top(), n, -1);

				if(mn != INF){
					sgt.update(stk.top(), n, -sgt.query(i, stk.top() - 1));

					int l = stk.top() - 1, r = n + 1, m;

					while(r - l > 1){
						m = l + (r - l) / 2;

						if(sgt.query(stk.top(), m) >= 0) r = m;
						else l = m;
					}

					fw.range_update(r, n, -1);

					sgt.update(stk.top(), n, sgt.query(i, stk.top() - 1));
				}

				stk.pop();
			}
		}
		else if(arr[i] == 'T'){
			mn = i;

			fw.range_update(i, n, 1);

			stk.push(i);
		}

		for(auto p : query[i]){
			ans[p.second] = fw.query(p.first);
		}
	}

	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12244 KB Output is correct
2 Correct 11 ms 12220 KB Output is correct
3 Correct 12 ms 12120 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 10 ms 12184 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12244 KB Output is correct
2 Correct 11 ms 12220 KB Output is correct
3 Correct 12 ms 12120 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 10 ms 12184 KB Output is correct
6 Correct 211 ms 18408 KB Output is correct
7 Correct 213 ms 17996 KB Output is correct
8 Correct 191 ms 18072 KB Output is correct
9 Correct 213 ms 18272 KB Output is correct
10 Correct 167 ms 18284 KB Output is correct
11 Correct 176 ms 18612 KB Output is correct
12 Correct 197 ms 18456 KB Output is correct
13 Correct 146 ms 18616 KB Output is correct
14 Correct 166 ms 18448 KB Output is correct
15 Correct 160 ms 18456 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12244 KB Output is correct
2 Correct 11 ms 12220 KB Output is correct
3 Correct 12 ms 12120 KB Output is correct
4 Correct 10 ms 12244 KB Output is correct
5 Correct 10 ms 12184 KB Output is correct
6 Correct 211 ms 18408 KB Output is correct
7 Correct 213 ms 17996 KB Output is correct
8 Correct 191 ms 18072 KB Output is correct
9 Correct 213 ms 18272 KB Output is correct
10 Correct 167 ms 18284 KB Output is correct
11 Correct 176 ms 18612 KB Output is correct
12 Correct 197 ms 18456 KB Output is correct
13 Correct 146 ms 18616 KB Output is correct
14 Correct 166 ms 18448 KB Output is correct
15 Correct 160 ms 18456 KB Output is correct
16 Correct 1874 ms 48740 KB Output is correct
17 Correct 1806 ms 44680 KB Output is correct
18 Correct 1840 ms 45800 KB Output is correct
19 Correct 1821 ms 47460 KB Output is correct
20 Correct 1623 ms 47640 KB Output is correct
21 Correct 1574 ms 50032 KB Output is correct
22 Correct 1677 ms 49220 KB Output is correct
23 Correct 1501 ms 49996 KB Output is correct
24 Correct 1421 ms 49028 KB Output is correct
25 Correct 1264 ms 48076 KB Output is correct