Submission #384508

#	Time	Username	Problem	Language	Result	Execution time	Memory
384508		LucaDantas	Teams (IOI15_teams)	C++17	34 / 100	4062 ms	10348 KiB

teams

#include "teams.h"
#include <queue>
#include <vector>
#include <algorithm>

constexpr int maxn = 1e5+10;

std::priority_queue<int, std::vector<int>, std::greater<int>> q;

int a[maxn], b[maxn], n;

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

struct Event
{
	int t, x, r;
	bool operator<(Event e) { if(x == e.x) return t < e.t; return x < e.x; }
};

std::vector<Event> events;

int can(int M, int K[]) {
	events.clear();
	while(q.size()) q.pop();
	for(int i = 0; i < n; i++)
		events.push_back({0, a[i], b[i]});
	for(int i = 0; i < M; i++)
		events.push_back({1, K[i], K[i]});
	std::sort(events.begin(), events.end());
	for(auto e : events) {
		while(q.size() && q.top() < e.x)
			q.pop();
		if(!e.t) q.push(e.r);
		else {
			while(e.r--) {
				if(!q.size()) return 0;
				q.pop();
			}
		}
	}
	return 1;
}

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