Submission #119649

#	Time	Username	Problem	Language	Result	Execution time	Memory
119649		MvC	Teams (IOI15_teams)	C++14	0 / 100	1084 ms	163168 KiB

teams

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#include "teams.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=5e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
vector<int>a[nmax];
int nlf(int x)
{
	int p=++nds;
	lch[p]=rch[p]=0;
	st[p]=x;
	return p;
}
int npr(int l,int r)
{
	int p=++nds;
	lch[p]=l,rch[p]=r;
	st[p]=st[l]+st[r];
	return p;
}
int upd(int nod,int l,int r,int p)
{
	if(l==r)return nlf(nr[l]);
	int mid=(l+r)/2;
	if(p<=mid)return npr(upd(lch[nod],l,mid,p),rch[nod]);
	else return npr(lch[nod],upd(rch[nod],mid+1,r,p));
}
int qry(int nod,int l,int r,int tl,int tr)
{
	if(tr<l || tl>r)return 0;
	if(tl<=l && r<=tr)return st[nod];
	int mid=(l+r)/2;
	int v=0;
	if(tl<=mid)v=qry(lch[nod],l,mid,tl,tr);
	if(tr>mid)v+=qry(rch[nod],mid+1,r,tl,tr);
	return v;
}
void init(int N,int A[],int B[])
{
	n=N;
	for(i=1;i<=n;i++)
	{
		x=A[i-1],y=B[i-1];
		a[x].pb(y);
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<a[i].size();j++)
		{
			nr[a[i][j]]++;
			rt[++r]=upd(rt[r-1],1,n,a[i][j]);
		}
		nd[i]=rt[r];
	}
}
int can(int M,int K[])
{
	m=M;
	for(i=1;i<=m;i++)k[i]=K[i-1];
	sort(k+1,k+m+1);
	s=0;
	for(i=1;i<=m;i++)
	{
		s+=k[i];
		if(!(qry(nd[k[i]],1,n,k[i],n)>=k[i] && qry(nd[k[i]],1,n,k[1],n)>=s))break;
	}
	if(i==m+1)return 1;
	return 0;
}

Compilation message (stderr)

teams.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
teams.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
teams.cpp: In function 'int nlf(int)':
teams.cpp:24:14: warning: declaration of 'x' shadows a global declaration [-Wshadow]
 int nlf(int x)
              ^
teams.cpp:22:69: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                     ^
teams.cpp: In function 'int npr(int, int)':
teams.cpp:31:20: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int npr(int l,int r)
                    ^
teams.cpp:22:77: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                             ^
teams.cpp: In function 'int upd(int, int, int, int)':
teams.cpp:38:34: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int upd(int nod,int l,int r,int p)
                                  ^
teams.cpp:22:77: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                             ^
teams.cpp: In function 'int qry(int, int, int, int, int)':
teams.cpp:45:42: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int qry(int nod,int l,int r,int tl,int tr)
                                          ^
teams.cpp:22:77: note: shadowed declaration is here
 int n,i,nr[nmax],st[10*20*nmax],lch[10*20*nmax],rch[10*20*nmax],q,t,x,y,nds,r,rt[nmax],nd[nmax],m,s,j,k[nmax];
                                                                             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:65:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<a[i].size();j++)
           ~^~~~~~~~~~~~
teams.cpp:68:7: warning: operation on 'r' may be undefined [-Wsequence-point]
    rt[++r]=upd(rt[r-1],1,n,a[i][j]);
       ^~~

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