Submission #746719

#	Time	Username	Problem	Language	Result	Execution time	Memory
746719		Username4132	Teams (IOI15_teams)	C++14	34 / 100	4032 ms	20292 KiB

teams

#include "teams.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define PB push_back
#define F first
#define S second

const int MAXN=500010, SQ=1010;
int n, aa[MAXN], bb[MAXN], uniq[SQ], req[SQ], arr[SQ][SQ];

void init(int N, int A[], int B[]) {
	n=N;
	forn(i, n) aa[i]=A[i], bb[i]=B[i];
}

int can(int m, int K[]) {
	int suu=0, sz=0;
	forn(i, m){
		suu+=K[i];
		if(suu>n) return 0;
	}
	sort(K, K+m);
	forn(i, m){
		if(i==0 || K[i]!=K[i-1]) uniq[sz]=K[i], req[sz]=1, ++sz;
		else req[sz-1]++;
	}
	forn(i, sz) req[i]*=uniq[i];
	forn(i, sz) forsn(j, i, sz) arr[i][j]=0;
	
	forn(i, n){
		int l = lower_bound(uniq, uniq+sz, aa[i]) - uniq;
		int r = (upper_bound(uniq, uniq+sz, bb[i]) - uniq) - 1;
		if(l<=r) arr[l][r]++;
	}
	forn(i, sz){
		forsn(j, i, sz){
			if(req[i]>arr[i][j]) req[i]-=arr[i][j], arr[i][j]=0;
			else{
				arr[i][j]-=req[i];
				req[i]=0;
				break;
			}
		}
		if(req[i]>0) return 0;
		forsn(j, i+1, sz) arr[i+1][j]+=arr[i][j];
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:37:45: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   37 |   int l = lower_bound(uniq, uniq+sz, aa[i]) - uniq;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
teams.cpp:38:54: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   38 |   int r = (upper_bound(uniq, uniq+sz, bb[i]) - uniq) - 1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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