Submission #1089942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089942		Tob	Teams (IOI15_teams)	C++14	0 / 100	4075 ms	151640 KiB

teams

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

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

const int N = 5e5 + 7;

int n, no;
int t[63*N], le[63*N], ri[63*N], root[N];
vector <int> doda[N];

void update(int x, int y, int pos, int val, int lo = 0, int hi = N-1) {
	if (lo == hi) {
		t[x] = t[y] + val;
		return;
	}
	int mid = (lo + hi) / 2;
	if (pos <= mid) {
		le[x] = no++;
		ri[x] = ri[y];
		update(le[x], le[y], pos, val, lo, mid);
	}
	else {
		le[x] = le[y];
		ri[x] = no++;
		update(ri[x], ri[y], pos, val, mid+1, hi);
	}
	t[x] = t[le[x]]+t[ri[x]];
}

void add(int x, int pos, int val) {
	int y = root[x];
	root[x] = no++;
	update(root[x], y, pos, val);
}

pii get(int x, int y, int a, int b, int k = N, int lo = 0, int hi = N-1) {
	if (b < lo || hi < a || !y) return {-1, 0};
	if (a <= lo && hi <= b && t[y]-t[x] < k) return {-1, t[y]-t[x]};
	if (lo == hi) return {lo, 1};
	int mid = (lo + hi) / 2;
	pii p = get(le[x], le[y], a, b, k, lo, mid);
	if (p.F != -1) return p;
	pii p2 = get(ri[x], ri[y], a, b, k-p.S, mid+1, hi);
	return {p2.F, p.S+p2.S};
}

void init(int n_, int A[], int B[]) {
	n = n_; no = 1;
	root[0] = no++;
	for (int i = 0; i < n; i++) doda[A[i]].pb(B[i]);
	for (int i = 1; i <= n; i++) {
		root[i] = root[i-1];
		for (int x : doda[i]) add(i, x, 1);
	}
}

int can(int m, int K[]) {
	vector <int> dp(m+1, 0), wh(m, -1);
	set <pii> s;
	set <int> p;
	for (int i = 0; i < m; i++) {
		pii p1 = get(root[0], root[K[i]], K[i], N-1);
		dp[i+1] = p1.S-K[i];
		
		for (int j = 0; j < i; j++) {
			p1 = get(root[j+1], root[K[i]], K[i], N-1);
			dp[i+1] = min(dp[i+1], dp[j]+p1.S-K[i]);
		}
	}
	return (dp[m] >= 0);
}

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