oj.uz

Submission #765237

# Submission time Handle Problem Language Result Execution time Memory
765237 2023-06-24T09:41:53 Z SanguineChameleon Teams (IOI15_teams) C++17
100 / 100
 1578 ms 154528 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 5e5 + 20;
const int maxL = 20;
const int maxM = 2e5 + 20;
vector<int> add[maxN];
int tree[maxN * maxL];
int ch[maxN * maxL][2];
int root[maxN * 4];
int dp[maxM];
int node_cnt;
int N;

int update(int cur_id, int lt, int rt, int pos) {
	int new_id = ++node_cnt;
	if (lt == rt) {
		tree[new_id] = tree[cur_id] + 1;
		return new_id;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		ch[new_id][0] = update(ch[cur_id][0], lt, mt, pos);
		ch[new_id][1] = ch[cur_id][1];
	}
	else {
		ch[new_id][0] = ch[cur_id][0];
		ch[new_id][1] = update(ch[cur_id][1], mt + 1, rt, pos);
	}
	tree[new_id] = tree[ch[new_id][0]] + tree[ch[new_id][1]];
	return new_id;
}

void init(int _N, int A[], int B[]) {
	N = _N;
	for (int i = 0; i < N; i++) {
		add[B[i]].push_back(A[i]);
	}
	for (int i = N; i >= 1; i--) {
		root[i] = root[i + 1];
		for (auto pos: add[i]) {
			root[i] = update(root[i], 1, N, pos);
		}
	}
}

int get(int id, int lt, int rt, int ql, int qr) {
	if (lt == ql && rt == qr) {
		return tree[id];
	}
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		return get(ch[id][0], lt, mt, ql, qr);
	}
	else if (ql >= mt + 1) {
		return get(ch[id][1], mt + 1, rt, ql, qr);
	}
	else {
		return get(ch[id][0], lt, mt, ql, mt) + get(ch[id][1], mt + 1, rt, mt + 1, qr);
	}
}

int get(int lx, int rx, int ly) {
	if (lx > rx) {
		return 0;
	}
	return get(root[ly], 1, N, lx, rx);
}

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> events;

int *K;

void add_bad(int i, int j) {
	int lt = K[j] + 1;
	int rt = N;
	int T = N + 1;
	while (lt <= rt) {
		int mt = (lt + rt) / 2;
		if (get(K[i] + 1, K[j], mt) <= dp[j] - dp[i]) {
			T = mt;
			rt = mt - 1;
		}
		else {
			lt = mt + 1;
		}
	}
	events.emplace(T, -j - 1);
}

int can(int M, int _K[]) {
	K = _K;
	long long sum = 0;
	for (int i = 0; i < M; i++) {
		sum += K[i];
	}
	if (sum > N) {
		return 0;
	}
	sort(K, K + M);
	set<int> S;
	while (!events.empty()) {
		events.pop();
	}
	for (int i = 0; i < M; i++) {
		events.emplace(K[i], i);
	}
	while (!events.empty()) {
		int id = events.top().second;
		events.pop();
		if (id >= 0) {
			dp[id] = get(1, K[id], K[id]) - K[id];
			if (!S.empty()) {
				int best = *S.rbegin();
				dp[id] = min(dp[id], dp[best] + get(K[best] + 1, K[id], K[id]) - K[id]);
			}
			if (dp[id] < 0) {
				return false;
			}
			if (!S.empty()) {
				add_bad(*S.rbegin(), id);
			}
			S.insert(id);
		}
		else {
			id = -id - 1;
			auto it = S.find(id);
			if (it == S.end()) {
				continue;
			}
			if (it != S.begin() && next(it) != S.end()) {
				add_bad(*prev(it), *next(it));
			}
			S.erase(it);
		}
	}
	return true;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 5 ms 11988 KB Output is correct
3 Correct 5 ms 12024 KB Output is correct
4 Correct 6 ms 12056 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 6 ms 12092 KB Output is correct
8 Correct 7 ms 12052 KB Output is correct
9 Correct 6 ms 12020 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 6 ms 11988 KB Output is correct
12 Correct 9 ms 12116 KB Output is correct
13 Correct 6 ms 11988 KB Output is correct
14 Correct 7 ms 11988 KB Output is correct
15 Correct 6 ms 12052 KB Output is correct
16 Correct 6 ms 11988 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 6 ms 11988 KB Output is correct
19 Correct 6 ms 12048 KB Output is correct
20 Correct 6 ms 12044 KB Output is correct
21 Correct 6 ms 11988 KB Output is correct
22 Correct 7 ms 11988 KB Output is correct
23 Correct 7 ms 11988 KB Output is correct
24 Correct 6 ms 12052 KB Output is correct
25 Correct 6 ms 11988 KB Output is correct
26 Correct 6 ms 12056 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 36072 KB Output is correct
2 Correct 46 ms 36000 KB Output is correct
3 Correct 52 ms 35952 KB Output is correct
4 Correct 47 ms 37608 KB Output is correct
5 Correct 26 ms 34908 KB Output is correct
6 Correct 26 ms 34932 KB Output is correct
7 Correct 26 ms 34884 KB Output is correct
8 Correct 30 ms 34880 KB Output is correct
9 Correct 41 ms 37108 KB Output is correct
10 Correct 33 ms 36064 KB Output is correct
11 Correct 27 ms 35040 KB Output is correct
12 Correct 25 ms 35012 KB Output is correct
13 Correct 31 ms 34884 KB Output is correct
14 Correct 33 ms 35524 KB Output is correct
15 Correct 42 ms 35888 KB Output is correct
16 Correct 43 ms 35848 KB Output is correct
17 Correct 28 ms 35104 KB Output is correct
18 Correct 27 ms 35084 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 36400 KB Output is correct
2 Correct 67 ms 36428 KB Output is correct
3 Correct 96 ms 39868 KB Output is correct
4 Correct 49 ms 37520 KB Output is correct
5 Correct 191 ms 35320 KB Output is correct
6 Correct 136 ms 35324 KB Output is correct
7 Correct 34 ms 35276 KB Output is correct
8 Correct 118 ms 35340 KB Output is correct
9 Correct 38 ms 37052 KB Output is correct
10 Correct 63 ms 36444 KB Output is correct
11 Correct 70 ms 35540 KB Output is correct
12 Correct 129 ms 35392 KB Output is correct
13 Correct 302 ms 35440 KB Output is correct
14 Correct 310 ms 37708 KB Output is correct
15 Correct 175 ms 36408 KB Output is correct
16 Correct 181 ms 36436 KB Output is correct
17 Correct 140 ms 35568 KB Output is correct
18 Correct 162 ms 35552 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 145212 KB Output is correct
2 Correct 435 ms 145088 KB Output is correct
3 Correct 605 ms 151428 KB Output is correct
4 Correct 389 ms 147192 KB Output is correct
5 Correct 504 ms 139340 KB Output is correct
6 Correct 384 ms 139112 KB Output is correct
7 Correct 141 ms 139120 KB Output is correct
8 Correct 329 ms 143472 KB Output is correct
9 Correct 190 ms 152452 KB Output is correct
10 Correct 192 ms 142236 KB Output is correct
11 Correct 213 ms 141804 KB Output is correct
12 Correct 399 ms 142684 KB Output is correct
13 Correct 888 ms 145044 KB Output is correct
14 Correct 1578 ms 154528 KB Output is correct
15 Correct 591 ms 150588 KB Output is correct
16 Correct 598 ms 150696 KB Output is correct
17 Correct 402 ms 145140 KB Output is correct
18 Correct 402 ms 145048 KB Output is correct