Submission #908574

#	Time	Username	Problem	Language	Result	Execution time	Memory
908574		Mathias	Election (BOI18_election)	C++14	100 / 100	1088 ms	47772 KiB

election

#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 (stderr)

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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18