oj.uz

Submission #73871

# Submission time Handle Problem Language Result Execution time Memory
73871 2018-08-29T07:47:44 Z zscoder Election (BOI18_election) C++17
82 / 100
 1665 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;
 
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 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);
		//cerr<<"NODE : "<<l<<' '<<r-1<<'\n';
		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=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';
		}
		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].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:242: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:180: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:180: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:185: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:205: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 160 ms 192632 KB Output is correct
2 Correct 162 ms 192768 KB Output is correct
3 Correct 181 ms 192844 KB Output is correct
4 Correct 214 ms 192908 KB Output is correct
5 Correct 179 ms 192956 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 192632 KB Output is correct
2 Correct 162 ms 192768 KB Output is correct
3 Correct 181 ms 192844 KB Output is correct
4 Correct 214 ms 192908 KB Output is correct
5 Correct 179 ms 192956 KB Output is correct
6 Correct 363 ms 200984 KB Output is correct
7 Correct 320 ms 200984 KB Output is correct
8 Correct 282 ms 200984 KB Output is correct
9 Correct 283 ms 200984 KB Output is correct
10 Correct 301 ms 200984 KB Output is correct
11 Correct 370 ms 204436 KB Output is correct
12 Correct 303 ms 204560 KB Output is correct
13 Correct 326 ms 209168 KB Output is correct
14 Correct 336 ms 209168 KB Output is correct
15 Correct 386 ms 209168 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 192632 KB Output is correct
2 Correct 162 ms 192768 KB Output is correct
3 Correct 181 ms 192844 KB Output is correct
4 Correct 214 ms 192908 KB Output is correct
5 Correct 179 ms 192956 KB Output is correct
6 Correct 363 ms 200984 KB Output is correct
7 Correct 320 ms 200984 KB Output is correct
8 Correct 282 ms 200984 KB Output is correct
9 Correct 283 ms 200984 KB Output is correct
10 Correct 301 ms 200984 KB Output is correct
11 Correct 370 ms 204436 KB Output is correct
12 Correct 303 ms 204560 KB Output is correct
13 Correct 326 ms 209168 KB Output is correct
14 Correct 336 ms 209168 KB Output is correct
15 Correct 386 ms 209168 KB Output is correct
16 Correct 1665 ms 251148 KB Output is correct
17 Correct 1490 ms 258408 KB Output is correct
18 Runtime error 1457 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
19 Halted 0 ms 0 KB -