Submission #59577

#	Time	Username	Problem	Language	Result	Execution time	Memory
59577		TadijaSebez	Teams (IOI15_teams)	C++11	100 / 100	1619 ms	180640 KiB

teams

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=500050;
const int M=20*N;
int n,ls[M],rs[M],tsz,root[N],sum[M];
void Set(int p, int &c, int ss, int se, int qi)
{
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+1;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi);
	else Set(rs[p],rs[c],mid+1,se,qi);
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>se || ss>qe || qs>qe) return 0;
	if(qs<=ss && qe>=se) return sum[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int Get(int p, int c, int ss, int se, int qs, int qe)
{
	if(qs>se || ss>qe || qs>qe) return 0;
	if(qs<=ss && qe>=se) return sum[c]-sum[p];
	int mid=ss+se>>1;
	return Get(ls[p],ls[c],ss,mid,qs,qe)+Get(rs[p],rs[c],mid+1,se,qs,qe);
}
int Find(int p, int c, int ss, int se, int k)
{
	if(ss==se) return ss;
	int mid=ss+se>>1;
	if(sum[ls[c]]-sum[ls[p]]>=k) return Find(ls[p],ls[c],ss,mid,k);
	else return Find(rs[p],rs[c],mid+1,se,k-sum[ls[c]]+sum[ls[p]]);
}
vector<int> all[N];
void init(int m, int a[], int b[])
{
	n=m;int i,j;
	for(i=0;i<n;i++) all[a[i]].pb(b[i]);
	for(i=1;i<=n;i++)
	{
		root[i]=root[i-1];
		for(j=0;j<all[i].size();j++) Set(root[i],root[i],1,n,all[i][j]);
	}
}
int min(int a, int b){ return a>b?b:a;}
int val[N],cnt[N],used[N];
int x[N],y[N],push[N],top;
bool can(int m, int k[])
{
	int sum=0,i,j,sz=0;
	sort(k,k+m);
	for(i=0;i<m;i++)
	{
		sum+=k[i];
		if(sz && val[sz-1]==k[i]) cnt[sz-1]+=k[i];
		else val[sz]=cnt[sz]=k[i],sz++;
	}
	if(sum>n) return 0;
	m=sz;
	for(i=0;i<=m;i++) used[i]=0;
	val[m]=n+1;
	top=0;
	x[top]=0;y[top]=n;push[top]=0;top++;
	for(i=0;i<m;i++)
	{
		int need=cnt[i];
		int l=val[i];
		while(top && y[top-1]<val[i]) top--;
		int last=val[i]-1;
		while(top)
		{
			int add=Get(root[x[top-1]],root[val[i]],1,n,last+1,y[top-1])+push[top-1];
			if(add<need) need-=add;
			else break;
			last=y[top-1];
			top--;
		}
		if(!top) return 0;
		int t=Find(root[x[top-1]],root[val[i]],1,n,need+Get(root[x[top-1]],root[val[i]],1,n,1,last));
		t=min(t,y[top-1]);
		x[top]=val[i];
		y[top]=t;
		push[top]=Get(root[x[top-1]],root[val[i]],1,n,last+1,t)-need;
		top++;
		/*for(j=i;j<m;j++)
		{
			int have=Get(root[l],1,n,val[j],val[j+1]-1)-used[j];
			int add=min(have,need);
			need-=add;
			used[j]+=add;
			if(!need) break;
		}*/
		//if(need) return 0;
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void Set(int, int&, int, int, int)':
teams.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
teams.cpp: In function 'int Get(int, int, int, int, int)':
teams.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
teams.cpp: In function 'int Get(int, int, int, int, int, int)':
teams.cpp:28:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
teams.cpp: In function 'int Find(int, int, int, int, int)':
teams.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:46:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<all[i].size();j++) Set(root[i],root[i],1,n,all[i][j]);
           ~^~~~~~~~~~~~~~
teams.cpp: In function 'bool can(int, int*)':
teams.cpp:54:6: warning: declaration of 'sum' shadows a global declaration [-Wshadow]
  int sum=0,i,j,sz=0;
      ^~~
teams.cpp:8:31: note: shadowed declaration is here
 int n,ls[M],rs[M],tsz,root[N],sum[M];
                               ^~~
teams.cpp:71:7: warning: unused variable 'l' [-Wunused-variable]
   int l=val[i];
       ^
teams.cpp:54:14: warning: unused variable 'j' [-Wunused-variable]
  int sum=0,i,j,sz=0;
              ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23