Submission #60049

#	Time	Username	Problem	Language	Result	Execution time	Memory
60049		Kerim	Election (BOI18_election)	C++17	100 / 100	2208 ms	114524 KiB

election

#include "bits/stdc++.h"
#define MAXN 500009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
char sa[MAXN];
int suf[MAXN],pre[MAXN],dp[MAXN*2];
vector<PII>query[MAXN];
vector<int>adj[MAXN];
int s[MAXN<<2],lazy[MAXN<<2],ans[MAXN],n;
void build(int nd,int x,int y){
	if(x==y){
		s[nd]=suf[x];
		return;
	}
	int mid=(x+y)>>1;
	build(nd<<1,x,mid);
	build(nd<<1|1,mid+1,y);
	s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void shift(int nd){
	int &ret=lazy[nd];
	if(!ret)
		return;
	lazy[nd<<1]+=ret;s[nd<<1]+=ret;	
	lazy[nd<<1|1]+=ret;s[nd<<1|1]+=ret;	
	ret=0;
}
void inc(int l,int r,int v,int nd,int x,int y){
	if(l>y or x>r)
		return;
	if(l<=x and y<=r){
		s[nd]+=v;
		lazy[nd]+=v;
		return;
	}
	shift(nd);
	int mid=(x+y)>>1;
	inc(l,r,v,nd<<1,x,mid);
	inc(l,r,v,nd<<1|1,mid+1,y);
	s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
int tap(int l,int r,int nd,int x,int y){
	if(l>y or x>r)
		return INF;
	if(l<=x and y<=r)
		return s[nd];
	shift(nd);
	int mid=(x+y)>>1;
	return min(tap(l,r,nd<<1,x,mid),tap(l,r,nd<<1|1,mid+1,y));	
}
int P[MAXN][19];
int get(int x,int y){
	int res=0;
	for(int i=18;i>=0;i--)
		if(~P[x][i] and P[x][i]<=y)
			x=P[x][i],res+=(1<<i);
	return res;	
}
void dfs(int nd){
	tr(it,query[nd+1]){
		int r=it->ff,ind=it->ss;
		if(r==n)
			ans[ind]=max(0,-tap(nd+1,r,1,1,n));
		else
			ans[ind]=max(0,-tap(nd+1,r,1,1,n)+tap(r+1,r+1,1,1,n));	
		ans[ind]+=get(nd,r);
	}
	inc(1,nd,+1,1,1,n);
	for(int i=0;i<int(adj[nd].size());i++){
		int to=adj[nd][i];
		dfs(to);
	}
	inc(1,nd,-1,1,1,n);
}
int main(){
	memset(P,-1,sizeof P);
    //~ freopen("file.in", "r", stdin);
    scanf("%d",&n);
    scanf("%s",sa+1);
    for(int i=1;i<=n;i++){
		pre[i]=pre[i-1];
		if(sa[i]=='C')
			pre[i]++;
		else
			pre[i]--;
	}
	for(int i=n;i>=1;i--){
		suf[i]=suf[i+1];
		if(sa[i]=='C')
			suf[i]++;
		else
			suf[i]--;
	}
	vector<int>root;
	memset(dp,-1,sizeof dp);
	for(int i=n;i>=0;i--){
		if(~dp[pre[i]+n-1]){
			adj[dp[pre[i]+n-1]].pb(i);
			P[i][0]=dp[pre[i]+n-1];
			for(int j=1;j<=18;j++)
				if(~P[i][j-1])
					P[i][j]=P[P[i][j-1]][j-1];
		}
		else
			root.pb(i);
		dp[pre[i]+n]=i;
	}
	build(1,1,n);
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		query[l].pb(mp(r,i));
	}
	tr(it,root)
		dfs(*it);
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
    //~ int q;
    //~ scanf("%d",&q);
    //~ while(q--){
		//~ int l,r;
		//~ scanf("%d%d",&l,&r);
		//~ int last=l-1;
		//~ for(int i=l;i<=r;i++)
			//~ if(par[i]==par[last]-1){
				//~ last=i;
				//~ vis[i]=1;
			//~ }
		//~ int sum=0,mn=INF;
		//~ for(int i=r;i>=l;i--)
			//~ if(!vis[i]){
				//~ sum+=(s[i]=='C');
				//~ sum-=(s[i]=='T');
				//~ umin(mn,sum);
			//~ }
		//~ int ans=0;	
		//~ for(int i=l;i<=r;i++){
			//~ ans+=vis[i];
			//~ vis[i]=0;
		//~ }	
		//~ printf("%d\n",ans+max(0,-mn));
	//~ }
	return 0;
}

 

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
election.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",sa+1);
     ~~~~~^~~~~~~~~~~
election.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
election.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&l,&r);
   ~~~~~^~~~~~~~~~~~~~

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