Submission #529202

#	Time	Username	Problem	Language	Result	Execution time	Memory
529202		KoD	Teams (IOI15_teams)	C++17	100 / 100	931 ms	231924 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

template <class F> struct RecLambda : private F {
	explicit RecLambda(F&& f) : F(std::forward<F>(f)) {}
	template <class... Args> decltype(auto) operator()(Args&&... args) const {
		return F::operator()(*this, std::forward<Args>(args)...);
	}
};

struct Node {
	int count, left, right;
	Node() : count(0), left(0), right(0) {}
};

vector<Node> node = {Node()};

int size;
vector<int> roots;

int copy_node(const int k) {
	node.push_back(node[k]);
	return (int)node.size() - 1;
}

int add(const int k, const int i) {
	return RecLambda([&](auto&& dfs, const int n, const int a, const int b) -> int {
		const int u = copy_node(n);
		if (a + 1 == b) {
			node[u].count += 1;
		} else {
			const int m = (a + b) / 2;
			if (i < m) {
				node[u].left = dfs(node[u].left, a, m);
			} else {
				node[u].right = dfs(node[u].right, m, b);
			}
			node[u].count = node[node[u].left].count + node[node[u].right].count;
		}
		return u;
	})(k, 0, size + 1);
}

int fold(const int k, const int l, const int r) {
	return RecLambda([&](auto&& dfs, const int n, const int a, const int b) -> int {
		if (l <= a and b <= r) return node[n].count;
		if (b <= l or r <= a) return 0;
		const int m = (a + b) / 2;
		return dfs(node[n].left, a, m) + dfs(node[n].right, m, b);
	})(k, 0, size + 1);
}

int rect(const int l, const int r, const int d, const int u) {
	return fold(roots[r], d, u) - fold(roots[l], d, u);
}

void init(int N, int A[], int B[]) {
	size = N;
	vector<vector<int>> list(size + 1);
	for (int i = 0; i < N; ++i) {
		list[A[i]].push_back(B[i]);
	}
	int id = 0;
	roots.push_back(id);
	for (int x = 1; x <= N; ++x) {
		for (const int y : list[x]) {
			id = add(id, y);
		}
		roots.push_back(id);
	}
}

int can(int M, int K[]) {
	std::sort(K, K + M);
	struct Point {
		int x, y, c;
	};
	vector<Point> pts = {Point{0, size, 0}};
	for (int i = 0; i < M; ++i) {
		while (pts.back().y < K[i]) {
			pts.pop_back();
		}
		int xr = K[i], cr = rect(pts.back().x, K[i], 0, K[i]);
		while (true) {
			const auto [xl, yl, cl] = pts.back();
			if (rect(xl, xr, 0, yl + 1) - cr < K[i]) {
				if (xl == 0) return false;
				cr += cl;
				pts.pop_back();
			} else {
				int left = 0, right = size + 1, sum = 0;
				int u = roots[xr], v = roots[xl];
				while (right - left > 1) {
					const int add = node[node[u].left].count - node[node[v].left].count;
					if (sum + add - cr < K[i]) {
						sum += add;
						left = (left + right) / 2;
						u = node[u].right;
						v = node[v].right;
					} else {
						right = (left + right) / 2;
						u = node[u].left;
						v = node[v].left;
					}
				}
				pts.push_back(Point{xr, left, cr + K[i]});
				break;
			}
		}
	}
	return true;
}

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