Submission #295943

#	Time	Username	Problem	Language	Result	Execution time	Memory
295943		miss_robot	Teams (IOI15_teams)	C++14	34 / 100	4046 ms	44276 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

#pragma GCC optimize("O3")

using namespace std;

const int MAXN = 5e5;
int n;
tuple<int, int, int> a[MAXN];
pair<int, int> b[MAXN];

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

int can(int M, int K[]){
	sort(K, K+M);
	int pa = 0, pb = 0, pk = 0;
	set< pair<int, int> > q;
	while(pk < M){
		while(pa < n && get<0>(a[pa]) <= K[pk]) q.insert({get<1>(a[pa]), get<2>(a[pa])}), pa++;
		while(pb < n && b[pb].first < K[pk]) q.erase(b[pb]), pb++;
		if((int)q.size() < K[pk]) return 0;
		while(K[pk]--) q.erase(q.begin());
		pk++;
	}
	return 1;
}

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