Submission #604306

#	Time	Username	Problem	Language	Result	Execution time	Memory
604306		cheissmart	Teams (IOI15_teams)	C++14	34 / 100	4049 ms	64252 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 5e5 + 7;

int n;
int l[N], r[N];
V<pi> G[N];
vi asr[N];

void init(int _n, int _l[], int _r[]) {
	n = _n;
	for(int i = 0; i < n; i++)
		l[i] = _l[i], r[i] = _r[i];
	for(int i = 0; i < n; i++) {
		G[l[i]].EB(r[i], i);
		asr[r[i]].PB(i);
	}
}

int can(int m, int a[]) {
	if(accumulate(a, a + m, 0LL) > n) return 0;
	vi aux(n + 1);
	for(int i = 0; i < m; i++)
		aux[a[i]] += a[i];
	set<pi> s; // r, i
	for(int i = 1; i <= n; i++) {
		for(pi p:G[i]) s.insert(p);
		if(SZ(s) < aux[i]) return 0;
		for(int _ = 0; _ < aux[i]; _++)
			s.erase(s.begin());
		for(int id:asr[i])
			s.erase({i, id});
	}
	return 1;
}

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