Submission #59477

#	Time	Username	Problem	Language	Result	Execution time	Memory
59477		ngkan146	Teams (IOI15_teams)	C++11	34 / 100	4102 ms	75116 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
#define l first
#define r second

int n;
ii range[500000];

void init(int N, int A[], int B[]) {
	n = N;
	for(int i=0;i<n;i++)
		range[i] = {A[i], B[i]};
	sort(range, range+n);
}

int can(int m, int lst[]) {
	set <int> s;
	int tmp = 0;
	for(int i=0;i<m && tmp <= n && s.size() <= 448;i++){
		tmp = min(n+1, tmp + lst[i]);
		s.insert(lst[i]);
	}
	
	if (s.size() > 448 || tmp > n)	
		return 0;
		
	int newM = 0;
	int ask[500] = {}, askTimes[500] = {};
	
	for(set<int>::iterator it = s.begin(); it != s.end(); it++){
		ask[newM++] = *it;
	}
	for(int i=0;i<m;i++){
		askTimes[lower_bound(ask,ask+newM,lst[i]) - ask] ++;
	}
	
	multiset <int> current;
	int pivot = 0;
	for(int i=0;i<newM;i++){
		while(pivot < n && range[pivot].l <= ask[i]){
			current.insert(range[pivot++].r);
		}
		while(current.size() && *current.begin() < ask[i])
			current.erase(current.begin());
		
		if ((int)current.size() < ask[i] * askTimes[i])
			return 0;
		
		for(int _=0;_<ask[i] * askTimes[i];_++)
			current.erase(current.begin());
	}
	
	return 1;
}

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