oj.uz

Submission #73863

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

string s;
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)
	{
		cin>>n; cin>>s;
	}
	if(DEBUG)
	{
		srand(time(NULL));
		freopen("election_boi.in","w",stdout);
		n=100; 
		for(int i=0;i<n;i++) s+=(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; 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';
			cout<<ans<<'\n';
		}
		//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:238: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: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);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 192632 KB Output is correct
2 Correct 167 ms 192744 KB Output is correct
3 Correct 183 ms 192744 KB Output is correct
4 Correct 175 ms 192848 KB Output is correct
5 Correct 186 ms 192848 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 192632 KB Output is correct
2 Correct 167 ms 192744 KB Output is correct
3 Correct 183 ms 192744 KB Output is correct
4 Correct 175 ms 192848 KB Output is correct
5 Correct 186 ms 192848 KB Output is correct
6 Correct 606 ms 201532 KB Output is correct
7 Correct 647 ms 202404 KB Output is correct
8 Correct 562 ms 203264 KB Output is correct
9 Correct 489 ms 204248 KB Output is correct
10 Correct 615 ms 204248 KB Output is correct
11 Correct 542 ms 209540 KB Output is correct
12 Correct 524 ms 211116 KB Output is correct
13 Correct 565 ms 216384 KB Output is correct
14 Correct 492 ms 216384 KB Output is correct
15 Correct 556 ms 216384 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 192632 KB Output is correct
2 Correct 167 ms 192744 KB Output is correct
3 Correct 183 ms 192744 KB Output is correct
4 Correct 175 ms 192848 KB Output is correct
5 Correct 186 ms 192848 KB Output is correct
6 Correct 606 ms 201532 KB Output is correct
7 Correct 647 ms 202404 KB Output is correct
8 Correct 562 ms 203264 KB Output is correct
9 Correct 489 ms 204248 KB Output is correct
10 Correct 615 ms 204248 KB Output is correct
11 Correct 542 ms 209540 KB Output is correct
12 Correct 524 ms 211116 KB Output is correct
13 Correct 565 ms 216384 KB Output is correct
14 Correct 492 ms 216384 KB Output is correct
15 Correct 556 ms 216384 KB Output is correct
16 Execution timed out 3051 ms 263168 KB Time limit exceeded
17 Halted 0 ms 0 KB -