Submission #640011

#	Time	Username	Problem	Language	Result	Execution time	Memory
640011		ggoh	Teams (IOI15_teams)	C++14	100 / 100	939 ms	168316 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,sz;
vector<int>G[500005];
struct PST{
	int l,r,val;
}T[11000000];
int root[500005];
void initree(int num,int s,int e)
{
	if(s==e)return ;
	T[num].l=sz;
	T[sz++]={-1,-1,0};
	T[num].r=sz;
	T[sz++]={-1,-1,0};
	initree(T[num].l,s,(s+e)/2);
	initree(T[num].r,(s+e)/2+1,e);
}
void update(int par,int num,int s,int e,int x)
{
	T[num].val=T[par].val+1;
	if(s==e)return ;
	if(x<=(s+e)/2)
	{
		T[num].r=T[par].r;
		T[num].l=sz;
		T[sz++]={-1,-1,0};
		update(T[par].l,T[num].l,s,(s+e)/2,x);
	}
	else
	{
		T[num].l=T[par].l;
		T[num].r=sz;
		T[sz++]={-1,-1,0};
		update(T[par].r,T[num].r,(s+e)/2+1,e,x);
	}
}
struct D{
	int A,B;
}d[500005];
int go[500005];
bool cmp(D a,D b){return a.B<b.B;}
void init(int N, int A[], int B[]) {
	n=N;
	for(int i=0;i<n;i++)
	{
		d[i]={A[i],B[i]};
		go[i+1]=1e9;
	}
	sort(d,d+n,cmp);
	for(int i=0;i<n;i++)
	{
		go[d[i].B]=min(go[d[i].B],i+1);
		G[d[i].A].push_back(i+1);
	}
	for(int i=n-1;i>=1;i--)go[i]=min(go[i],go[i+1]);
	root[0]=sz;
	T[sz++]={-1,-1,0};
	initree(0,1,n);
	for(int i=1;i<=n;i++)
	{
		if(!sz(G[i]))
		{
			root[i]=root[i-1];
			continue;
		}
		int prev=root[i-1];
		for(auto &k:G[i])
		{
			root[i]=sz;
			T[sz++]={-1,-1,0};
			update(prev,root[i],1,n,k);
			prev=root[i];
		}
	}
}
int KTH,SZ;
struct C{
	int num1,num2,s,e,val;
}ST[50];
void getsum(int num1,int num2,int s,int e,int x1,int x2)
{
	if(s>x2||x1>e)return ;
	if(!T[num1].val && !T[num2].val)return ;
	if(x1<=s&&e<=x2)
	{
		ST[SZ++]={num1,num2,s,e,T[num2].val-T[num1].val};
		return ;
	}
	getsum(T[num1].l,T[num2].l,s,(s+e)/2,x1,x2);
	getsum(T[num1].r,T[num2].r,(s+e)/2+1,e,x1,x2);
}
int getind(int num1,int num2,int s,int e,int x1,int x2)
{
	if(s==e)
	{
		KTH--;
		return s;
	}
	if(T[T[num2].l].val-T[T[num1].l].val>=KTH)
	{
		return getind(T[num1].l,T[num2].l,s,(s+e)/2,x1,x2);
	}
	else
	{
		KTH-=T[T[num2].l].val-T[T[num1].l].val;
		return getind(T[num1].r,T[num2].r,(s+e)/2+1,e,x1,x2);
	}
}
int getK(int x1,int x2,int y1,int y2)
{
	SZ=0;
	getsum(root[y1-1],root[y2],1,n,x1,x2);
	for(int i=0;i<SZ;i++)
	{
		if(KTH>ST[i].val)KTH-=ST[i].val;
		else
		{
			return getind(ST[i].num1,ST[i].num2,ST[i].s,ST[i].e,x1,x2);
		}
	}
	return 1;
}
pii st[200002];
int stsz;
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);
	stsz=0;
	for(int i=0;i<m;i++)
	{
		while(stsz>0 && st[stsz-1].second<go[V[i].first])stsz--;
		KTH=V[i].second;
		int prev=go[V[i].first];
		while(stsz>=0)
		{
			if(stsz>0)t=getK(prev,st[stsz-1].second,st[stsz-1].first+1,V[i].first);
			else t=getK(prev,n,1,V[i].first);
			if(KTH>0)
			{
				if(stsz)prev=st[stsz-1].second+1;
				stsz--;
			}
			else
			{
				st[stsz++]={V[i].first,t};
				break;
			}
		}
		if(stsz==-1)
		{
			ans=0;
			break;
		}
	}
	return ans;
}

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