Submission #73875

#	Time	Username	Problem	Language	Result	Execution time	Memory
73875		zscoder	Election (BOI18_election)	C++17	100 / 100	1669 ms	142792 KiB

election

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
char s[555555];
int n;
int del[555555];
 
int solve_naive(int l, int r)
{
	int cnt=0;
	for(int i=l;i<=r;i++) del[i]=0;
	int ans=0; int S=0; int minpref=0;
	for(int i=l;i<=r;i++)
	{
		S+=(s[i]=='C'?1:-1);
		if(s[i]=='C') cnt++;
		else cnt--;
		if(cnt<0)
		{
			del[i]=1; ans++;
			cnt++;
		}
	}
	minpref=-ans;
	int positive = S - minpref;
	cnt=0; int mx=0;
	for(int i=r;i>=l;i--)
	{
		if(del[i]) 
		{
			cnt = positive; continue;
		}
		if(s[i]=='C') cnt++;
		else cnt--;
		if(cnt<0)
		{
			mx=max(mx,abs(cnt));	
		}
	}
	return ans+mx;
}
 
int vec[19][511111];
int sufmax[19][511111];
int prefmax[19][511111];
 
struct node
{
	int sum;
	//vi vec;
	//vi sufmax;
	int minprefback;
	//vi prefmax;
	int lvl;
	int l;
	int len;
	int lastneg;
};
 
node st[511111*4];
/*
void outnode(node S)
{
	cout<<"SUM : "<<S.sum<<'\n';
	for(int v:S.vec)
	{
		cout<<v<<' ';
	}
	cout<<'\n';
	cout<<"MIN PREF FROM BACK : "<<S.minprefback<<'\n';
	cout<<"LAST NEGATIVE : "<<S.lastneg<<'\n';
}
*/
node compute(int lvl, int l, int r)
{
	node N;
	N.l=l;
	N.lvl=lvl;
	N.sum=0;
	N.len=0;
	for(int i=l;i<=r;i++) del[i]=0;
	int cnt=0; int minpref=0;
	for(int i=l;i<=r;i++)
	{
		N.sum+=(s[i]=='C'?1:-1);
		cnt+=(s[i]=='C'?1:-1);
		if(cnt<0)
		{
			del[i]=1; cnt++; minpref--;
		}
	}
	N.minprefback=0; cnt=0;
	for(int i=r;i>=l;i--)
	{
		cnt+=(s[i]=='C'?1:-1);
		N.minprefback=min(N.minprefback, cnt);
	}
	N.minprefback*=-1;
	cnt=0; int mn = 0; bool ex=0; N.lastneg=0;
	for(int i=r;i>=l;i--)
	{
		if(del[i])
		{
			if(!ex)
			{
				N.lastneg=abs(mn);
			}
			else
			{
				vec[lvl][l + (N.len++)]=abs(mn);
			}
			cnt=0; mn=0;
			ex=1;
		}
		else
		{
			cnt+=(s[i]=='C'?1:-1);
			mn = min(mn, cnt);
		}
	}
	if(!ex)
	{
		N.lastneg = abs(mn);
	}
	else
	{
		vec[lvl][l + (N.len++)]=abs(mn);
	}
	int lef=l; int ri=l+N.len-1; 
	//cerr<<lef<<' '<<ri<<' '<<l<<' '<<r<<'\n';
	assert(ri<=r);
	int tmpl=lef; int tmpr=ri;
	while(lef<ri) 
	{
		swap(vec[lvl][lef],vec[lvl][ri]); lef++; ri--;
	}
	lef=tmpl; ri=tmpr;
	//N.sufmax.resize(int(N.vec.size()));
	for(int i=ri;i>=lef;i--)
	{
		sufmax[lvl][i] = vec[lvl][i];
		if(i+1<=ri) sufmax[lvl][i]=max(sufmax[lvl][i+1], sufmax[lvl][i]);
	}
	for(int i=lef;i<=ri;i++)
	{
		prefmax[lvl][i] = vec[lvl][i]-(i-lef);
		if(i>lef) prefmax[lvl][i]=max(prefmax[lvl][i-1],prefmax[lvl][i]);
	}
	return N;
}
 
void build(int id, int l, int r, int lvl=0)
{
	st[id] = compute(lvl,l,r-1);
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	build(id*2,l,mid,lvl+1); build(id*2+1,mid,r,lvl+1);
}
 
vi nodes;
void query(int id, int l, int r, int ql, int qr) //get which nodes i need to care for my query
{
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr) 
	{
		nodes.pb(id); return ;
	}
	int mid=(l+r)>>1;
	query(id*2,l,mid,ql,qr);
	query(id*2+1,mid,r,ql,qr);
}
const int DEBUG = 0;
int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);
	if(!DEBUG)
	{
		scanf("%d",&n); scanf("%s",s);
	}
	if(DEBUG)
	{
		srand(time(NULL));
		freopen("election_boi.in","w",stdout);
		n=10; 
		for(int i=0;i<n;i++) s[i] = (rand()&1?'C':'T');
	}
	if(DEBUG) cout<<n<<'\n'<<s<<'\n';
	int q; 
	if(!DEBUG) cin>>q;
	if(DEBUG) 
	{
		q=5;
		cout<<q<<'\n';
	}
	build(1,0,n);
	//outnode(st[1]);
	for(int i=0;i<q;i++)
	{
		int l,r; 
		if(!DEBUG)
		{
			//cin>>l>>r;
			scanf("%d %d",&l,&r); 
			l--; r--;
		}
		if(DEBUG)
		{
			l=rand()%n; r=rand()%n;
			if(l>r) swap(l,r);
			cout<<l+1<<' '<<r+1<<'\n';
		}
		nodes.clear(); query(1,0,n,l,r+1);
		int Lcnt = 0; 
		int Rcnt = 0;
		int maxmiddle = 0;
		int curL = 0; int minpref = 0;
		for(int v:nodes)
		{
			//curL of the vec elements will be rekted
			int badbrackets = st[v].len; int lvl = st[v].lvl; int l = st[v].l;
			//cerr<<"BAD : "<<badbrackets<<' '<<lvl<<' '<<l<<'\n';
			if(badbrackets==0)
			{
				minpref = max(st[v].lastneg, minpref - st[v].sum);
				curL += st[v].sum;
			}
			else
			{
				if(curL>=badbrackets)
				{
					minpref = max(st[v].minprefback, minpref - st[v].sum);
					curL-=badbrackets;
					curL+=st[v].sum+badbrackets;
				}
				else
				{
					maxmiddle = max(maxmiddle, prefmax[lvl][l+curL] + curL);
					maxmiddle = max(maxmiddle, minpref + curL);
					Lcnt += badbrackets - curL;
					if(curL+1<st[v].len) maxmiddle = max(maxmiddle, sufmax[lvl][l+curL+1]);
					curL = st[v].sum + badbrackets;
					minpref = st[v].lastneg;
				}
			}
			/*
			outnode(st[v]);
			cerr<<"MINPREF : "<<minpref<<'\n';
			cerr<<"CURL : "<<curL<<'\n';
			cerr<<"LCNT : "<<Lcnt<<'\n';
			cerr<<'\n';
			*/
		}
		Rcnt = max(Rcnt, max(minpref, maxmiddle - curL));
		int ans=Lcnt+Rcnt;
		if(DEBUG)
		{
			if(ans!=solve_naive(l,r))
			{
				assert(0);
				cerr<<"HERE"<<'\n';
			}
			cerr<<ans<<' '<<solve_naive(l,r)<<'\n';
		}
		else
		{
			//cout<<ans<<' '<<solve_naive(l,r)<<'\n';
			printf("%d\n",ans);
		}
		//cout<<solve(l,r)<<'\n';
	}
}	

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:193:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n); scanf("%s",s);
   ~~~~~^~~~~~~~~
election.cpp:193:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n); scanf("%s",s);
                   ~~~~~^~~~~~~~
election.cpp:198:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("election_boi.in","w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:218:9: 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