oj.uz

Submission #73875

# Submission time Handle Problem Language Result Execution time Memory
73875 2018-08-29T07:50:06 Z zscoder Election (BOI18_election) C++17
100 / 100
 1669 ms 142792 KB 
#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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 5 ms 1132 KB Output is correct
4 Correct 6 ms 1132 KB Output is correct
5 Correct 6 ms 1148 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 5 ms 1132 KB Output is correct
4 Correct 6 ms 1132 KB Output is correct
5 Correct 6 ms 1148 KB Output is correct
6 Correct 156 ms 18212 KB Output is correct
7 Correct 113 ms 18272 KB Output is correct
8 Correct 104 ms 18320 KB Output is correct
9 Correct 104 ms 18320 KB Output is correct
10 Correct 102 ms 18320 KB Output is correct
11 Correct 161 ms 19396 KB Output is correct
12 Correct 124 ms 19396 KB Output is correct
13 Correct 127 ms 19396 KB Output is correct
14 Correct 140 ms 19396 KB Output is correct
15 Correct 120 ms 19396 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1016 KB Output is correct
2 Correct 6 ms 1132 KB Output is correct
3 Correct 5 ms 1132 KB Output is correct
4 Correct 6 ms 1132 KB Output is correct
5 Correct 6 ms 1148 KB Output is correct
6 Correct 156 ms 18212 KB Output is correct
7 Correct 113 ms 18272 KB Output is correct
8 Correct 104 ms 18320 KB Output is correct
9 Correct 104 ms 18320 KB Output is correct
10 Correct 102 ms 18320 KB Output is correct
11 Correct 161 ms 19396 KB Output is correct
12 Correct 124 ms 19396 KB Output is correct
13 Correct 127 ms 19396 KB Output is correct
14 Correct 140 ms 19396 KB Output is correct
15 Correct 120 ms 19396 KB Output is correct
16 Correct 1108 ms 98656 KB Output is correct
17 Correct 1062 ms 106000 KB Output is correct
18 Correct 1132 ms 106156 KB Output is correct
19 Correct 1000 ms 113176 KB Output is correct
20 Correct 1039 ms 115820 KB Output is correct
21 Correct 1669 ms 139656 KB Output is correct
22 Correct 1183 ms 139656 KB Output is correct
23 Correct 1443 ms 142792 KB Output is correct
24 Correct 1105 ms 142792 KB Output is correct
25 Correct 1000 ms 142792 KB Output is correct