oj.uz

Submission #73864

# Submission time Handle Problem Language Result Execution time Memory
73864 2018-08-29T07:23:16 Z zscoder Election (BOI18_election) C++17
82 / 100
 3000 ms 254264 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;
}


struct node
{
	int sum;
	vi vec;
	vi sufmax;
	int minprefback;
	vi prefmax;
	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 l, int r)
{
	node N;
	N.sum=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
			{
				N.vec.pb(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
	{
		N.vec.pb(abs(mn));
	}
	reverse(N.vec.begin(),N.vec.end());
	N.sufmax.resize(int(N.vec.size()));
	for(int i=int(N.vec.size())-1;i>=0;i--)
	{
		N.sufmax[i] = N.vec[i];
		if(i+1<N.vec.size()) N.sufmax[i]=max(N.sufmax[i+1], N.sufmax[i]);
	}
	N.prefmax.resize(int(N.vec.size()));
	for(int i=0;i<N.vec.size();i++)
	{
		N.prefmax[i] = N.vec[i]-i;
		if(i>0) N.prefmax[i]=max(N.prefmax[i-1],N.prefmax[i]);
	}
	return N;
}

void build(int id, int l, int r)
{
	st[id] = compute(l,r-1);
	if(r-l<2) return ;
	int mid=(l+r)>>1;
	build(id*2,l,mid); build(id*2+1,mid,r);
}

vi 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) 
	{
		//cerr<<"NODE : "<<l<<' '<<r-1<<'\n';
		return {id};
	}
	int mid=(l+r)>>1;
	vi L=query(id*2,l,mid,ql,qr);
	vi R=query(id*2+1,mid,r,ql,qr);
	for(int x:R) L.pb(x);
	return L;
}
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=100; 
		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=500;
		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';
		}
		vector<int> nodes = 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].vec.size();
			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, st[v].prefmax[curL] + curL);
					maxmiddle = max(maxmiddle, minpref + curL);
					Lcnt += badbrackets - curL;
					if(curL+1<st[v].sufmax.size()) maxmiddle = max(maxmiddle, st[v].sufmax[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 'node compute(int, int)':
election.cpp:140:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1<N.vec.size()) N.sufmax[i]=max(N.sufmax[i+1], N.sufmax[i]);
      ~~~^~~~~~~~~~~~~
election.cpp:143:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<N.vec.size();i++)
              ~^~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:240:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(curL+1<st[v].sufmax.size()) maxmiddle = max(maxmiddle, st[v].sufmax[curL+1]);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
election.cpp:179: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:179: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:184: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:204: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 186 ms 192760 KB Output is correct
2 Correct 188 ms 192760 KB Output is correct
3 Correct 187 ms 192760 KB Output is correct
4 Correct 207 ms 192760 KB Output is correct
5 Correct 202 ms 192952 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 192760 KB Output is correct
2 Correct 188 ms 192760 KB Output is correct
3 Correct 187 ms 192760 KB Output is correct
4 Correct 207 ms 192760 KB Output is correct
5 Correct 202 ms 192952 KB Output is correct
6 Correct 609 ms 201464 KB Output is correct
7 Correct 591 ms 202288 KB Output is correct
8 Correct 567 ms 203188 KB Output is correct
9 Correct 503 ms 203844 KB Output is correct
10 Correct 629 ms 203844 KB Output is correct
11 Correct 718 ms 207420 KB Output is correct
12 Correct 714 ms 207896 KB Output is correct
13 Correct 566 ms 212204 KB Output is correct
14 Correct 691 ms 212204 KB Output is correct
15 Correct 661 ms 212204 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 192760 KB Output is correct
2 Correct 188 ms 192760 KB Output is correct
3 Correct 187 ms 192760 KB Output is correct
4 Correct 207 ms 192760 KB Output is correct
5 Correct 202 ms 192952 KB Output is correct
6 Correct 609 ms 201464 KB Output is correct
7 Correct 591 ms 202288 KB Output is correct
8 Correct 567 ms 203188 KB Output is correct
9 Correct 503 ms 203844 KB Output is correct
10 Correct 629 ms 203844 KB Output is correct
11 Correct 718 ms 207420 KB Output is correct
12 Correct 714 ms 207896 KB Output is correct
13 Correct 566 ms 212204 KB Output is correct
14 Correct 691 ms 212204 KB Output is correct
15 Correct 661 ms 212204 KB Output is correct
16 Execution timed out 3038 ms 254264 KB Time limit exceeded
17 Halted 0 ms 0 KB -