Submission #1090136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090136		Tob	Teams (IOI15_teams)	C++14	100 / 100	706 ms	172112 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[]) {
	sort(K, K+m);
	vector <int> dp(m+1, 0), wh(m, -1);
	set <pii> s;
	set <int> p;
	int mn = 0;
	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];
		
		while (!s.empty() && s.begin() -> F <= K[i]) {
			int x = s.begin() -> S;
			int y = *(++p.find(x));
			p.erase(y);
			s.erase(s.begin());
			if (++p.find(x) != p.end()) {
				int z = *(++p.find(x));
				s.erase({wh[y], y});
				pii p2 = get(root[K[x]], root[K[z]], K[z], N-1);
				if (dp[x+1]+p2.S <= dp[z+1]) s.insert({(wh[x]=-1), x});
				else {
					pii p3 = get(root[K[x]], root[K[z]], K[z], N-1, dp[x+1]+p2.S-dp[z+1]);
					if (p3.F == -1) s.insert({wh[x]=N-1, x});
					else s.insert({wh[x]=p3.F+1, x});
				}
			}
		}
		if (i) {
			int z = *(--p.end());
			pii p2 = get(root[K[z]], root[K[i]], K[i], N-1);
			dp[i+1] = min(dp[i+1], dp[z+1]+p2.S-K[i]);
			if (dp[z+1]+p2.S <= dp[i+1]) s.insert({wh[z]=-1, z});
			else {
				pii p3 = get(root[K[z]], root[K[i]], K[i], N-1, dp[z+1]+p2.S-dp[i+1]);
				if (p3.F == -1) s.insert({wh[z]=N-1, z});
				else s.insert({wh[z]=p3.F+1, z});
			}
		}
		p.insert(i);
		mn = min(mn, dp[i+1]);
	}
	return (mn >= 0);
}

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