oj.uz

답안 #73868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73868 2018-08-29T07:40:04 Z zscoder Election (BOI18_election) C++17
82 / 100
 3000 ms 101732 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[20][511111];
int sufmax[20][511111];
int prefmax[20][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 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=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';
		}
		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].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:195: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:195: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:200: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:220: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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1016 KB Output is correct
2 Correct 10 ms 1016 KB Output is correct
3 Correct 13 ms 1016 KB Output is correct
4 Correct 10 ms 1200 KB Output is correct
5 Correct 13 ms 1200 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1016 KB Output is correct
2 Correct 10 ms 1016 KB Output is correct
3 Correct 13 ms 1016 KB Output is correct
4 Correct 10 ms 1200 KB Output is correct
5 Correct 13 ms 1200 KB Output is correct
6 Correct 407 ms 18456 KB Output is correct
7 Correct 415 ms 18456 KB Output is correct
8 Correct 418 ms 18456 KB Output is correct
9 Correct 371 ms 18456 KB Output is correct
10 Correct 387 ms 18456 KB Output is correct
11 Correct 443 ms 19420 KB Output is correct
12 Correct 374 ms 19420 KB Output is correct
13 Correct 359 ms 19448 KB Output is correct
14 Correct 370 ms 19448 KB Output is correct
15 Correct 535 ms 19448 KB Output is correct

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1016 KB Output is correct
2 Correct 10 ms 1016 KB Output is correct
3 Correct 13 ms 1016 KB Output is correct
4 Correct 10 ms 1200 KB Output is correct
5 Correct 13 ms 1200 KB Output is correct
6 Correct 407 ms 18456 KB Output is correct
7 Correct 415 ms 18456 KB Output is correct
8 Correct 418 ms 18456 KB Output is correct
9 Correct 371 ms 18456 KB Output is correct
10 Correct 387 ms 18456 KB Output is correct
11 Correct 443 ms 19420 KB Output is correct
12 Correct 374 ms 19420 KB Output is correct
13 Correct 359 ms 19448 KB Output is correct
14 Correct 370 ms 19448 KB Output is correct
15 Correct 535 ms 19448 KB Output is correct
16 Execution timed out 3052 ms 101732 KB Time limit exceeded
17 Halted 0 ms 0 KB -