Submission #639980

#	Time	Username	Problem	Language	Result	Execution time	Memory
639980		ggoh	Teams (IOI15_teams)	C++14	34 / 100	4104 ms	524288 KiB

teams

#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;

int n,xsz,ysz;

struct X2D{
	int l,r,ynum;
};
struct Y2D{
	int l,r,val;
};
vector<X2D>X;
vector<Y2D>Y;
void yupdate(int ynum,int s,int e,int y)
{
	Y[ynum].val++;
	if(s==e)return ;
	if(y<=(s+e)/2)
	{
		if(Y[ynum].l==-1)
		{
			Y[ynum].l=ysz++;
			Y.push_back({-1,-1,0});
		}
		yupdate(Y[ynum].l,s,(s+e)/2,y);
	}
	else
	{
		if(Y[ynum].r==-1)
		{
			Y[ynum].r=ysz++;
			Y.push_back({-1,-1,0});
		}
		yupdate(Y[ynum].r,(s+e)/2+1,e,y);
	}
}
void xupdate(int xnum,int s,int e,int x,int y)
{
	yupdate(X[xnum].ynum,1,n,y);
	if(s==e)return ;
	if(x<=(s+e)/2)
	{
		if(X[xnum].l==-1)
		{
			X[xnum].l=xsz++;
			X.push_back({-1,-1,ysz++});
			Y.push_back({-1,-1,0});
		}
		xupdate(X[xnum].l,s,(s+e)/2,x,y);
	}
	else
	{
		if(X[xnum].r==-1)
		{
			X[xnum].r=xsz++;
			X.push_back({-1,-1,ysz++});
			Y.push_back({-1,-1,0});
		}
		xupdate(X[xnum].r,(s+e)/2+1,e,x,y);
	}
}
int gety(int ynum,int s,int e,int y1,int y2)
{
	if(ynum==-1)return 0;
	if(y1>e || s>y2)return 0;
	if(y1<=s && e<=y2)return Y[ynum].val;
	return gety(Y[ynum].l,s,(s+e)/2,y1,y2)+gety(Y[ynum].r,(s+e)/2+1,e,y1,y2);
}
int getx(int xnum,int s,int e,int x1,int x2,int y1,int y2)
{
	if(xnum==-1)return 0;
	if(x1>e || s>x2)return 0;
	if(x1<=s && e<=x2)return gety(X[xnum].ynum,1,n,y1,y2);
	return getx(X[xnum].l,s,(s+e)/2,x1,x2,y1,y2)+getx(X[xnum].r,(s+e)/2+1,e,x1,x2,y1,y2);
}
void init(int N, int A[], int B[]) {
	n=N;
	xsz++;
	X.push_back({-1,-1,ysz++});
	Y.push_back({-1,-1,0});
	for(int i=0;i<n;i++)xupdate(0,1,n,B[i],A[i]);
}
int rem[200002];
int can(int M, int K[]) {
	
	lint sum=0;
	for(int i=0;i<M;i++)sum+=K[i];
	if(sum>n)return 0;
	int ans=1,t;
	sort(K,K+M);
	t=K[0];
	vector<pii>V;
	for(int i=1;i<M;i++)
	{
		if(K[i]==K[i-1])
		{
			t+=K[i];
		}
		else
		{
			V.push_back({K[i-1],t});
			t=K[i];
		}
	}
	V.push_back({K[M-1],t});
	int m=sz(V);
	for(int i=0;i<m;i++)rem[i]=V[i].second;
	for(int i=m-1;i>=0;i--)
	{
		int r=0,t;
		for(int j=m-1;j>=i+1;j--)
		{
			if(!rem[j])continue;
			t=getx(0,1,n,V[j].first,n,i==0?1:(V[i-1].first+1),V[i].first)-r;
			if(rem[j]<t)t=rem[j];
			r+=t;
			rem[j]-=t;
		}
		t=getx(0,1,n,V[i].first,n,i==0?1:(V[i-1].first+1),V[i].first)-r;
		if(rem[i]<t)t=rem[i];
		rem[i]-=t;
	}
	for(int i=0;i<m;i++)if(rem[i])ans=0;
	return ans;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:114:11: warning: declaration of 't' shadows a previous local [-Wshadow]
  114 |   int r=0,t;
      |           ^
teams.cpp:93:12: note: shadowed declaration is here
   93 |  int ans=1,t;
      |            ^

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