Submission #384560

#	Time	Username	Problem	Language	Result	Execution time	Memory
384560		LucaDantas	Teams (IOI15_teams)	C++17	0 / 100	4070 ms	10220 KiB

teams

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

constexpr int maxn = 1e5+10, SZ = 100;

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

int a[maxn], b[maxn], ativos[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 greedy(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;
// }

bool intersect(int l1, int r1, int l2, int r2) {
	if(l1 > r2 || r1 < l2) return 0;
	return 1;
}

int unicos(int l, int r) {
	int ans = 0;
	for(int i = 0; i < n; i++)
		if(intersect(a[i], b[i], l, r)) ++ans;
	return ans;
}

struct BIT
{
	int bit[maxn];
	void upd(int x, int v) {
		for(; x < maxn; x += x&-x)
			bit[x] += v;
	}
	int query(int x) {
		int ans = 0;
		for(; x > 0; x -= x&-x)
			ans += bit[x];
		return ans;
	}
	int itv(int l, int r) { return query(r) - query(l-1); }
} bit;

int can(int M, int K[]) {
	// if(M > SZ) return greedy(M, K);
	for(int i = 0; i < M; i++)
		bit.upd(K[i], K[i]);
	std::sort(K, K+M);
	for(int i = 0; i < M; i++) {
		for(int j = i; j < M; j++) {
			if(unicos(K[i], K[j]) < bit.itv(K[i], K[j])) return 0;
		}
	}
	for(int i = 0; i < M; i++)
		bit.upd(K[i], -K[i]);
	return 1;
}

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