Submission #70698

#	Time	Username	Problem	Language	Result	Execution time	Memory
70698		Sa1378	Teams (IOI15_teams)	C++17	0 / 100	4048 ms	10988 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define N ((int)101*1000)
#define K ((int)22)
#define SQ ((int)500)

int n,pos[N];
pair <int,int> a[N];
int seg[K][N];

void build(int xl=0,int xr=n,int h=0)
{
	if(xl==xr-1)
	{
		seg[h][xl]=a[xl].second;
		return ;
	}
	int mid=(xl+xr)/2;
	build(xl,mid,h+1);
	build(mid,xr,h+1);
	merge(seg[h+1]+xl,seg[h+1]+mid,seg[h+1]+mid,seg[h+1]+xr,seg[h]+xl);
}

int query(int q,int val,int xl=0,int xr=n,int h=0)
{
	int res=0;
	for(int i=0;i<q;i++)
		if(a[i].second>=val)
			res++;
	return res;/*
	if(xr<=q)return xr-(lower_bound(seg[h]+xl,seg[h]+xr,val)-(seg[h]+xl));
	int mid=(xl+xr)/2;
	int res=query(q,val,xl,mid,h+1);
	if(mid<q)res+=query(q,val,mid,xr,h+1);
	return res;*/
}

void init(int n2, int A[], int B[])
{
	n=n2;
	for(int i=0;i<n;i++)a[i]={A[i],B[i]};
	sort(a,a+n);
	for(int i=1,j=0;i<=n;i++)
	{
		while(j<n && a[j].first<=i)j++;
		pos[i]=j;
	}
	//build();
}

pair <int,int> b[N];
int cnt[SQ][SQ];

int can(int m, int k[])
{
	int m2=0,sum=0;
	sort(k,k+m);
	for(int i=0;i<m;i++)sum+=k[i];
	if(sum>n)return 0;
	for(int i=0;i<m;i++)
	{
		b[m2]={k[i],0};
		while(i<m && k[i]==b[m2].first)b[m2].second+=k[i],i++;
		m2++;
	}
	m=m2;
	for(int i=0;i<m;i++)
		for(int j=i;j<m;j++)
			cnt[i][j]=query(pos[b[i].first],b[j].first);
	for(int i=m-1;i>=0;i--)
		for(int j=i;j<m;j++)
			cnt[i][j]+=-cnt[i][j+1]-((i>0)?cnt[i-1][j]:0)+((i>0)?cnt[i-1][j+1]:0);
	for(int i=0;i<m;i++)
	{
//		cout<<i<<"||| \n";
//		for(int j=0;j<m;j++)cout<<cnt[i][j]<<"\n";
		int j=i;
		for(;j<m;j++)
		{
//			cout<<b[i].second<<" "<<cnt[i][j]
			if(b[i].second<=cnt[i][j])
			{
//				cout<<"hir";
				cnt[i][j]-=b[i].second;
				b[i].second=0;
				break;
			}
			b[i].second-=cnt[i][j];
		}
//		cout<<b[i].second<<"..\n";
		if(b[i].second)return 0;
		for(;j<m;j++)cnt[i+1][j]+=cnt[i][j];
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:25:32: warning: unused parameter 'xl' [-Wunused-parameter]
 int query(int q,int val,int xl=0,int xr=n,int h=0)
                                ^
teams.cpp:25:41: warning: unused parameter 'xr' [-Wunused-parameter]
 int query(int q,int val,int xl=0,int xr=n,int h=0)
                                         ^
teams.cpp:25:49: warning: unused parameter 'h' [-Wunused-parameter]
 int query(int q,int val,int xl=0,int xr=n,int h=0)
                                                 ^

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