Submission #986387

#	Time	Username	Problem	Language	Result	Execution time	Memory
986387		Pyqe	Teams (IOI15_teams)	C++17	100 / 100	1690 ms	250012 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

int n,nsg=0,nn,fq[500069],la[30000069],ra[30000069],sma[30000069],pa[30000069][2],sg[500069],inf=1e9;
pair<int,int> a[2][500069],sk[200069];

void bd(int ix,int lh,int rh)
{
	la[ix]=lh;
	ra[ix]=rh;
	sma[ix]=0;
	if(la[ix]!=ra[ix])
	{
		int ii,md=(la[ix]+ra[ix])/2;
		
		for(ii=0;ii<2;ii++)
		{
			nsg++;
			pa[ix][ii]=nsg;
			bd(nsg,!ii?la[ix]:md+1,!ii?md:ra[ix]);
		}
	}
}

void ud(int ix,int x,int w)
{
	if(la[ix]>=x&&ra[ix]<=x)
	{
		sma[ix]+=w;
	}
	else
	{
		int ii,jj,p;
		
		for(ii=0;ii<2;ii++)
		{
			p=pa[ix][ii];
			if(la[p]<=x&&ra[p]>=x)
			{
				nsg++;
				la[nsg]=la[p];
				ra[nsg]=ra[p];
				sma[nsg]=sma[p];
				for(jj=0;jj<2;jj++)
				{
					pa[nsg][jj]=pa[p][jj];
				}
				pa[ix][ii]=nsg;
				ud(nsg,x,w);
			}
		}
		sma[ix]=sma[pa[ix][0]]+sma[pa[ix][1]];
	}
}

int qr(int ix,int lh,int rh,int sr)
{
	if(la[ix]>rh||ra[ix]<lh)
	{
		return 0;
	}
	else if(la[ix]>=lh&&ra[ix]<=rh)
	{
		return sma[ix]-sma[sr];
	}
	else
	{
		return qr(pa[ix][0],lh,rh,pa[sr][0])+qr(pa[ix][1],lh,rh,pa[sr][1]);
	}
}

int bl(int ix,int x,int sr)
{
	if(la[ix]==ra[ix])
	{
		return la[ix];
	}
	else
	{
		int ii,p,p2;
		
		for(ii=0;ii<2;ii++)
		{
			p=pa[ix][ii];
			p2=pa[sr][ii];
			if(x<=sma[p]-sma[p2])
			{
				return bl(p,x,p2);
			}
			x-=sma[p]-sma[p2];
		}
		return -1;
	}
}

void init(int on,int laa[],int raa[])
{
	int i,ii,k,l;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		k=laa[i-1];
		l=raa[i-1];
		a[0][i]={k,l};
	}
	sort(a[0]+1,a[0]+n+1);
	for(i=1;i<=n;i++)
	{
		l=a[0][i].sc;
		fq[l]++;
		a[1][i]={l,fq[l]};
	}
	sort(a[1]+1,a[1]+n+1);
	for(i=n;i;i--)
	{
		l=a[0][i].sc;
		a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
		fq[l]--;
	}
	nsg++;
	sg[0]=nsg;
	bd(nsg,1,n);
	for(i=1;i<=n;i++)
	{
		l=a[0][i].sc;
		nsg++;
		la[nsg]=la[sg[i-1]];
		ra[nsg]=ra[sg[i-1]];
		sma[nsg]=sma[sg[i-1]];
		for(ii=0;ii<2;ii++)
		{
			pa[nsg][ii]=pa[sg[i-1]][ii];
		}
		sg[i]=nsg;
		ud(nsg,l,1);
	}
}

int can(int sz,int qq[])
{
	int i,k,l,w,sm;
	
	sort(qq,qq+sz);
	nn=0;
	for(i=0;i<sz;i++)
	{
		sm=qq[i];
		k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
		l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
		for(;nn;nn--)
		{
			w=qr(sg[k],l+1,sk[nn].sc-1,sg[sk[nn].fr]);
			if(w>sm)
			{
				break;
			}
			l=max(l,sk[nn].sc);
			sm-=w;
		}
		l=bl(sg[k],qr(sg[k],1,l,sg[sk[nn].fr])+sm,sg[sk[nn].fr]);
		if(l==-1)
		{
			return 0;
		}
		nn++;
		sk[nn]={k,l};
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:124:54: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  124 |   a[0][i].sc=lower_bound(a[1]+1,a[1]+n+1,mp(l,fq[l]))-a[1];
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:155:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  155 |   k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:156:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  156 |   l=lower_bound(a[1]+1,a[1]+n+1,mp(sm,0))-a[1]-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

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