oj.uz

Submission #134256

# Submission time Handle Problem Language Result Execution time Memory
134256 2019-07-22T09:54:39 Z mirbek01 Election (BOI18_election) C++11
100 / 100
 2696 ms 53212 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 3;

struct node{
	int sum, mn;
	node(){
		sum = mn = 0;
	}
}
t[N * 4];

int n;
string s;
int q, ans[N];
vector < pair <int, int> > qe[N];
vector <int> st;
node _new;

node combine(node a, node b){
	a.mn = min(b.mn, a.mn + b.sum);
	a.sum += b.sum;
	return a;
}

void build(int v = 1, int tl = 1, int tr = n){
	if(tl == tr){
		t[v].sum = (s[tl] == 'C'?1:-1);
		t[v].mn = t[v].sum;
	} else {
		int tm = (tl + tr) >> 1;
		build(v << 1, tl, tm);
		build(v << 1 | 1, tm + 1, tr);
		t[v] = combine(t[v << 1], t[v << 1 | 1]);
	}
}

void upd(int pos, int val, int v = 1, int tl = 1, int tr = n){
	if(tl == tr){
		t[v].sum = t[v].mn = val;
	} else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			upd(pos, val, v << 1, tl, tm);
		else 
			upd(pos, val, v << 1 | 1, tm + 1, tr);
		t[v] = combine(t[v << 1], t[v << 1 | 1]);
	}
}

node get(int l, int r, int v = 1, int tl = 1, int tr = n){
	if(l > tr || tl > r)
		return _new;
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) >> 1;
	return combine(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr));
}

int main(){
	cin >> n >> s >> q;
	
	s = ' ' + s;
	
	for(int i = 1; i <= q; i ++){
		int l, r;
		cin >> l >> r;
		qe[l].emplace_back(r, i);
	}
	
	build();
	
	for(int i = n; i >= 1; i --){
		if(s[i] == 'T'){
			st.push_back(i);
			upd(i, 0);
		} else if(!st.empty()){
			upd(st.back(), -1);
			st.pop_back();
		} 
		for(int j = 0; j < (int)qe[i].size(); j ++){
			int ret = upper_bound(st.rbegin(), st.rend(), qe[i][j].first) - st.rbegin();
			ret -= min(get(i, qe[i][j].first).mn, 0); 	
			ans[ qe[i][j].second ] = ret;
		}
	}
	
	for(int i = 1; i <= q; i ++)
		cout << ans[i] << endl;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27896 KB Output is correct
2 Correct 34 ms 27768 KB Output is correct
3 Correct 34 ms 27768 KB Output is correct
4 Correct 34 ms 27740 KB Output is correct
5 Correct 35 ms 27896 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27896 KB Output is correct
2 Correct 34 ms 27768 KB Output is correct
3 Correct 34 ms 27768 KB Output is correct
4 Correct 34 ms 27740 KB Output is correct
5 Correct 35 ms 27896 KB Output is correct
6 Correct 349 ms 30812 KB Output is correct
7 Correct 327 ms 30268 KB Output is correct
8 Correct 333 ms 30476 KB Output is correct
9 Correct 340 ms 30836 KB Output is correct
10 Correct 341 ms 30732 KB Output is correct
11 Correct 354 ms 31160 KB Output is correct
12 Correct 347 ms 30836 KB Output is correct
13 Correct 349 ms 31192 KB Output is correct
14 Correct 343 ms 30876 KB Output is correct
15 Correct 337 ms 30808 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 27896 KB Output is correct
2 Correct 34 ms 27768 KB Output is correct
3 Correct 34 ms 27768 KB Output is correct
4 Correct 34 ms 27740 KB Output is correct
5 Correct 35 ms 27896 KB Output is correct
6 Correct 349 ms 30812 KB Output is correct
7 Correct 327 ms 30268 KB Output is correct
8 Correct 333 ms 30476 KB Output is correct
9 Correct 340 ms 30836 KB Output is correct
10 Correct 341 ms 30732 KB Output is correct
11 Correct 354 ms 31160 KB Output is correct
12 Correct 347 ms 30836 KB Output is correct
13 Correct 349 ms 31192 KB Output is correct
14 Correct 343 ms 30876 KB Output is correct
15 Correct 337 ms 30808 KB Output is correct
16 Correct 2533 ms 50436 KB Output is correct
17 Correct 2379 ms 46508 KB Output is correct
18 Correct 2451 ms 47656 KB Output is correct
19 Correct 2438 ms 49200 KB Output is correct
20 Correct 2506 ms 49860 KB Output is correct
21 Correct 2598 ms 52288 KB Output is correct
22 Correct 2531 ms 51548 KB Output is correct
23 Correct 2696 ms 53212 KB Output is correct
24 Correct 2504 ms 51960 KB Output is correct
25 Correct 2487 ms 50716 KB Output is correct