oj.uz

Submission #908574

# Submission time Handle Problem Language Result Execution time Memory
908574 2024-01-16T14:41:06 Z Mathias Election (BOI18_election) C++14
100 / 100
 1088 ms 47772 KB 
#include <bits/stdc++.h>
using namespace std;
const int BASE = 1<<19;
const int INF = 1e9+7;
int tree[2*BASE],tree2[2*BASE],ans[BASE],suf[BASE];
vector<pair<int,int> > z[BASE];
vector<int> lista;
void push(int v,int l,int r){
	tree[l]+=tree2[v];
	tree[r]+=tree2[v];
	tree2[l]+=tree2[v];
	tree2[r]+=tree2[v];
	tree2[v]=0;
}
void add(int v,int p,int k,int a,int b,int x){
	if(k<a || p>b) return;
	else if(a<=p && k<=b){
		tree[v]+=x;
		tree2[v]+=x;
	}
	else{
		int l=2*v, r=2*v+1, mid=(p+k)/2;
		push(v,l,r);
		add(l,p,mid,a,b,x);
		add(r,mid+1,k,a,b,x);
		tree[v]=min(tree[l],tree[r]);
	}
}
int query(int v,int p,int k,int a,int b){
	if(k<a || p>b) return INF;
	else if(a<=p && k<=b) return tree[v];
	else{
		int l=2*v, r=2*v+1, mid=(p+k)/2;
		push(v,l,r);
		return min(query(l,p,mid,a,b), query(r,mid+1,k,a,b));
	}
}
int BS(int x){
	int s,p=0, k=lista.size()-1,res=0;
	while(p<=k){
		s=(p+k)/2;
		if(lista[s]<=x){
			res=lista.size()-s;
			k=s-1;
		}
		else p=s+1;
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n,q,a,b,x,xd,xd1;
	string s;
	cin>>n>>s>>q;
	s="#"+s;
	for(int i=1;i<=q;i++){
		cin>>a>>b;
		z[a].push_back({b,i});
	}
	for(int i=n;i>=1;i--){
		if(s[i]=='T') suf[i]=suf[i+1]-1;
		else suf[i]=suf[i+1]+1;
		add(1,0,BASE-1,i,i,suf[i]);
	}
	for(int i=n;i>=1;i--){
		if(s[i]=='T'){
			lista.push_back(i);
			add(1,0,BASE-1,1,i,1);
		}
		else if(lista.size()){
			x=lista[lista.size()-1];
			lista.pop_back();
			add(1,0,BASE-1,1,x,-1);	
		}
		for(auto e:z[i]){
			xd=query(1,0,BASE-1,i,e.first)-query(1,0,BASE-1,e.first+1,e.first+1);
			if(lista.size()) ans[e.second]=BS(e.first);
			if(xd<0) ans[e.second]-=xd;	
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:52:19: warning: unused variable 'xd1' [-Wunused-variable]
   52 |  int n,q,a,b,x,xd,xd1;
      |                   ^~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 9 ms 21144 KB Output is correct
3 Correct 9 ms 21080 KB Output is correct
4 Correct 10 ms 21080 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 9 ms 21144 KB Output is correct
3 Correct 9 ms 21080 KB Output is correct
4 Correct 10 ms 21080 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Correct 113 ms 22352 KB Output is correct
7 Correct 104 ms 22052 KB Output is correct
8 Correct 104 ms 21844 KB Output is correct
9 Correct 101 ms 22044 KB Output is correct
10 Correct 104 ms 22096 KB Output is correct
11 Correct 119 ms 22440 KB Output is correct
12 Correct 110 ms 22344 KB Output is correct
13 Correct 109 ms 22644 KB Output is correct
14 Correct 110 ms 22408 KB Output is correct
15 Correct 94 ms 22348 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 21084 KB Output is correct
2 Correct 9 ms 21144 KB Output is correct
3 Correct 9 ms 21080 KB Output is correct
4 Correct 10 ms 21080 KB Output is correct
5 Correct 8 ms 21084 KB Output is correct
6 Correct 113 ms 22352 KB Output is correct
7 Correct 104 ms 22052 KB Output is correct
8 Correct 104 ms 21844 KB Output is correct
9 Correct 101 ms 22044 KB Output is correct
10 Correct 104 ms 22096 KB Output is correct
11 Correct 119 ms 22440 KB Output is correct
12 Correct 110 ms 22344 KB Output is correct
13 Correct 109 ms 22644 KB Output is correct
14 Correct 110 ms 22408 KB Output is correct
15 Correct 94 ms 22348 KB Output is correct
16 Correct 988 ms 45276 KB Output is correct
17 Correct 753 ms 41392 KB Output is correct
18 Correct 838 ms 42432 KB Output is correct
19 Correct 889 ms 44128 KB Output is correct
20 Correct 887 ms 44632 KB Output is correct
21 Correct 1088 ms 47448 KB Output is correct
22 Correct 905 ms 46584 KB Output is correct
23 Correct 965 ms 47772 KB Output is correct
24 Correct 955 ms 46896 KB Output is correct
25 Correct 951 ms 45744 KB Output is correct