Submission #800652

#	Time	Username	Problem	Language	Result	Execution time	Memory
800652		firewater	Teams (IOI15_teams)	C++14	0 / 100	4067 ms	18428 KiB

teams

#include "teams.h"
#include<queue>
#include <stdio.h>
#include <stdlib.h>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;












#define MX 500500
#define fs first
#define sn second
#define mp make_pair
const ll B=500;
ll n,m,r,now,num,mx,k[MX],b[B+50][B+50];
pair<ll,ll>a[MX];
priority_queue<ll>d;
void init(int N, int AA[], int BB[]) {
	n=N;
	for(ll i=1;i<=n;++i)
		a[i]=mp(AA[i-1],BB[i-1]);
	sort(a+1,a+1+n);
	for(ll i=1;i<=n;++i)
		if(a[i].fs<=B)b[a[i].fs][min(a[i].sn,B)]++;
	for(ll i=2;i<=B;++i)
		for(ll j=i;j<=B;++j)
			b[i][j]+=b[i-1][j];
	for(ll i=1;i<=B;++i)
		for(ll j=B-1;j>=i;--j)
			b[i][j]+=b[i][j+1];
	return;
}

int can(int M, int K[]) {
	m=M;
	for(ll i=1;i<=m;++i)
		k[i]=K[i-1];
	
	sort(k+1,k+1+m);
	mx=0;
	for(ll i=1;i<=m;++i)
		mx=max(mx,k[i]);
	if(mx>B){
		r=1;
		while(!d.empty())d.pop();
		for(ll i=1;i<=m;++i){
			while(r<=n&&a[r].fs<=k[i]){
				d.push(-a[r].sn);
				r++;
			}
			while(!d.empty()&&-d.top()<k[i])d.pop();
			if(d.size()>=k[i]){
				now=k[i];
				while(now--)d.pop();
			}
			else return 0;
		}
		return 1;
	}
	else{
		k[0]=0;
		num=0;
		for(ll i=1;i<=m;++i){
			num=min(num,b[k[i-1]][k[i]])+b[k[i]][k[i]]-b[k[i-1]][k[i]];
			if(num<k[i])return 0;
			num-=k[i];
		}
		return 1;
	}
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:65:15: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   65 |    if(d.size()>=k[i]){
      |       ~~~~~~~~^~~~~~

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