oj.uz

Submission #529202

# Submission time Handle Problem Language Result Execution time Memory
529202 2022-02-22T11:48:01 Z KoD Teams (IOI15_teams) C++17
100 / 100
 931 ms 231924 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 288 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 0 ms 292 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 31408 KB Output is correct
2 Correct 82 ms 31292 KB Output is correct
3 Correct 68 ms 31396 KB Output is correct
4 Correct 66 ms 31620 KB Output is correct
5 Correct 39 ms 29620 KB Output is correct
6 Correct 38 ms 29668 KB Output is correct
7 Correct 37 ms 29676 KB Output is correct
8 Correct 39 ms 29668 KB Output is correct
9 Correct 50 ms 29632 KB Output is correct
10 Correct 49 ms 29356 KB Output is correct
11 Correct 37 ms 29352 KB Output is correct
12 Correct 40 ms 29484 KB Output is correct
13 Correct 48 ms 29836 KB Output is correct
14 Correct 50 ms 30424 KB Output is correct
15 Correct 64 ms 31156 KB Output is correct
16 Correct 62 ms 31140 KB Output is correct
17 Correct 39 ms 29848 KB Output is correct
18 Correct 45 ms 29832 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 31656 KB Output is correct
2 Correct 73 ms 31584 KB Output is correct
3 Correct 227 ms 31560 KB Output is correct
4 Correct 75 ms 31492 KB Output is correct
5 Correct 75 ms 29812 KB Output is correct
6 Correct 70 ms 29844 KB Output is correct
7 Correct 46 ms 29796 KB Output is correct
8 Correct 67 ms 29796 KB Output is correct
9 Correct 52 ms 29672 KB Output is correct
10 Correct 86 ms 29476 KB Output is correct
11 Correct 87 ms 29536 KB Output is correct
12 Correct 90 ms 29704 KB Output is correct
13 Correct 125 ms 30120 KB Output is correct
14 Correct 205 ms 31020 KB Output is correct
15 Correct 99 ms 31340 KB Output is correct
16 Correct 98 ms 31272 KB Output is correct
17 Correct 78 ms 30044 KB Output is correct
18 Correct 80 ms 29980 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 231924 KB Output is correct
2 Correct 523 ms 231912 KB Output is correct
3 Correct 899 ms 231880 KB Output is correct
4 Correct 536 ms 231904 KB Output is correct
5 Correct 312 ms 220128 KB Output is correct
6 Correct 304 ms 220204 KB Output is correct
7 Correct 241 ms 220212 KB Output is correct
8 Correct 288 ms 220196 KB Output is correct
9 Correct 354 ms 220976 KB Output is correct
10 Correct 340 ms 219092 KB Output is correct
11 Correct 342 ms 219640 KB Output is correct
12 Correct 363 ms 220240 KB Output is correct
13 Correct 542 ms 222424 KB Output is correct
14 Correct 931 ms 229036 KB Output is correct
15 Correct 495 ms 230048 KB Output is correct
16 Correct 510 ms 230076 KB Output is correct
17 Correct 332 ms 222184 KB Output is correct
18 Correct 335 ms 222156 KB Output is correct