Submission #986372

#	Time	Username	Problem	Language	Result	Execution time	Memory
986372		Pyqe	Teams (IOI15_teams)	C++17	77 / 100	1180 ms	524288 KiB

teams

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

using namespace std;

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

int n,nn,fq[500069],inf=1e9;
pair<int,int> a[2][500069],sk[200069];

struct segtree
{
	int l,r,sm;
	segtree *p[2];
	
	void bd(int lh,int rh)
	{
		l=lh;
		r=rh;
		sm=0;
		if(l!=r)
		{
			int ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
		}
	}
	void ud(int x,int w)
	{
		if(l>=x&&r<=x)
		{
			sm+=w;
		}
		else
		{
			int ii;
			segtree *tmp;
			
			for(ii=0;ii<2;ii++)
			{
				if(p[ii]->l<=x&&p[ii]->r>=x)
				{
					tmp=p[ii];
					p[ii]=new segtree;
					*p[ii]=*tmp;
					p[ii]->ud(x,w);
				}
			}
			sm=p[0]->sm+p[1]->sm;
		}
	}
	int qr(int lh,int rh,segtree *sr)
	{
		if(l>rh||r<lh)
		{
			return 0;
		}
		else if(l>=lh&&r<=rh)
		{
			return sm-sr->sm;
		}
		else
		{
			return p[0]->qr(lh,rh,sr->p[0])+p[1]->qr(lh,rh,sr->p[1]);
		}
	}
	int bl(int x,segtree *sr)
	{
		if(l==r)
		{
			return l;
		}
		else
		{
			int ii;
			
			for(ii=0;ii<2;ii++)
			{
				if(x<=p[ii]->sm-sr->p[ii]->sm)
				{
					return p[ii]->bl(x,sr->p[ii]);
				}
				x-=p[ii]->sm-sr->p[ii]->sm;
			}
			return -1;
		}
	}
}
sg[500069];

void init(int on,int la[],int ra[])
{
	int i,k,l;
	
	n=on;
	for(i=1;i<=n;i++)
	{
		k=la[i-1];
		l=ra[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]--;
	}
	sg[0].bd(1,n);
	for(i=1;i<=n;i++)
	{
		l=a[0][i].sc;
		sg[i]=sg[i-1];
		sg[i].ud(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=sg[k].qr(l+1,sk[nn].sc-1,&sg[sk[nn].fr]);
			if(w>sm)
			{
				break;
			}
			l=max(l,sk[nn].sc);
			sm-=w;
		}
		l=sg[k].bl(sg[k].qr(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:119:54: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  119 |   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:140:49: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  140 |   k=upper_bound(a[0]+1,a[0]+n+1,mp(sm,inf))-a[0]-1;
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:141:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  141 |   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: 0 / 23