Submission #908543

#	Time	Username	Problem	Language	Result	Execution time	Memory
908543		Mathias	Election (BOI18_election)	C++14	0 / 100	3006 ms	21080 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){
	if(lista[lista.size()-1]>x) return 0;
	if(lista[0]<=x) return lista.size();
	int s,p=0, k=lista.size()-1;
	while(p<k){
		s=(p+k)/2;
		if(lista[s]<x) p=s;
		else k=s-1;
	}
	return p;
}
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);	
			}
		}
		//cout<<"i="<<i<<" lista:"<<'\n'; for(int j=0;j<lista.size();j++) cout<<lista[j]<<' '; cout<<'\n';
		//cout<<"i="<<i<<" drzewo:"<<'\n';
		//for(int j=1;j<2*BASE;j++) cout<<j<<' '<<tree[j]<<' '<<tree2[j]<<'\n'; 
		//cout<<i<<' '<<z[i].size()<<'\n';
		for(auto e:z[i]){
			xd=query(1,0,BASE-1,i,e.first);
			xd1=query(1,0,BASE-1,e.first+1,e.first+1);
			xd-=xd1;
			if(lista.size()) ans[e.second]=BS(e.first);
			//cout<<e.first<<' '<<e.second<<' '<<lista.size()<<' '<<ans[e.second]<<' '<<xd<<'\n';
			if(xd<0){
				ans[e.second]-=xd;	
			} 
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
	return 0;
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18