Submission #712380

#	Time	Username	Problem	Language	Result	Execution time	Memory
712380		Johann	Teams (IOI15_teams)	C++14	34 / 100	4038 ms	19068 KiB

teams

#include "teams.h"

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

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<int> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

vpii S;
void init(int N, int A[], int B[])
{
	S.resize(N);
	for (int i = 0; i < N; ++i)
		S[i] = {A[i], B[i]};
	sort(all(S));
}

int can(int M, int K[])
{
	sort(K, K + M);
	priority_queue<int, vi, greater<int>> pq; // b : end of interval
	int idx = 0;
	for (int i = 0; i < M; ++i)
	{
		int todo = K[i];
		while (idx < sz(S) && S[idx].first <= K[i])
			pq.push(S[idx++].second);
		while (todo)
		{
			if (pq.empty())
				return 0;
			if (pq.top() >= K[i])
				--todo;
			pq.pop();
		}
	}
	return 1;
}

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