Submission #800673

#	Time	Username	Problem	Language	Result	Execution time	Memory
800673		firewater	Teams (IOI15_teams)	C++14	34 / 100	4059 ms	18364 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,x,now,num,mx,k[MX],s[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];
	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{
		for(int i=1;i<=B;++i)
			s[i]=0;
		for(int i=1;i<=m;++i){
			now=k[i];
			for(int j=k[i];j<=B;++j){
				x=min(b[k[i]][j]-s[j],now);
				now-=x;
				s[j]+=x;
				if(!now)break;
			}
			if(now)return 0;
		}
		return 1;
	}
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:67: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]
   67 |    if(d.size()>=k[i]){
      |       ~~~~~~~~^~~~~~
teams.cpp:80:17: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |    for(int j=k[i];j<=B;++j){
      |              ~~~^

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