oj.uz

Submission #1090136

# Submission time Handle Problem Language Result Execution time Memory
1090136 2024-09-17T19:17:33 Z Tob Teams (IOI15_teams) C++14
100 / 100
 706 ms 172112 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12176 KB Output is correct
4 Correct 5 ms 12240 KB Output is correct
5 Correct 5 ms 12124 KB Output is correct
6 Correct 10 ms 13104 KB Output is correct
7 Correct 6 ms 12188 KB Output is correct
8 Correct 5 ms 12124 KB Output is correct
9 Correct 6 ms 12380 KB Output is correct
10 Correct 5 ms 12124 KB Output is correct
11 Correct 6 ms 12120 KB Output is correct
12 Correct 6 ms 12124 KB Output is correct
13 Correct 5 ms 12124 KB Output is correct
14 Correct 6 ms 12124 KB Output is correct
15 Correct 5 ms 12124 KB Output is correct
16 Correct 5 ms 12164 KB Output is correct
17 Correct 6 ms 12124 KB Output is correct
18 Correct 5 ms 12224 KB Output is correct
19 Correct 6 ms 12124 KB Output is correct
20 Correct 6 ms 12124 KB Output is correct
21 Correct 5 ms 12124 KB Output is correct
22 Correct 5 ms 12120 KB Output is correct
23 Correct 5 ms 12124 KB Output is correct
24 Correct 5 ms 12120 KB Output is correct
25 Correct 5 ms 12120 KB Output is correct
26 Correct 5 ms 12228 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 39680 KB Output is correct
2 Correct 49 ms 39664 KB Output is correct
3 Correct 47 ms 39508 KB Output is correct
4 Correct 92 ms 50344 KB Output is correct
5 Correct 26 ms 38116 KB Output is correct
6 Correct 27 ms 38196 KB Output is correct
7 Correct 27 ms 38196 KB Output is correct
8 Correct 29 ms 38100 KB Output is correct
9 Correct 49 ms 41568 KB Output is correct
10 Correct 35 ms 39624 KB Output is correct
11 Correct 27 ms 37844 KB Output is correct
12 Correct 26 ms 37832 KB Output is correct
13 Correct 36 ms 38328 KB Output is correct
14 Correct 36 ms 38624 KB Output is correct
15 Correct 45 ms 39508 KB Output is correct
16 Correct 48 ms 39508 KB Output is correct
17 Correct 28 ms 38228 KB Output is correct
18 Correct 30 ms 38444 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 40340 KB Output is correct
2 Correct 93 ms 40564 KB Output is correct
3 Correct 115 ms 43856 KB Output is correct
4 Correct 92 ms 50284 KB Output is correct
5 Correct 73 ms 38992 KB Output is correct
6 Correct 73 ms 38888 KB Output is correct
7 Correct 71 ms 38996 KB Output is correct
8 Correct 72 ms 38792 KB Output is correct
9 Correct 49 ms 41416 KB Output is correct
10 Correct 78 ms 40136 KB Output is correct
11 Correct 73 ms 38596 KB Output is correct
12 Correct 81 ms 38748 KB Output is correct
13 Correct 109 ms 39376 KB Output is correct
14 Correct 132 ms 42096 KB Output is correct
15 Correct 106 ms 40280 KB Output is correct
16 Correct 107 ms 40312 KB Output is correct
17 Correct 93 ms 38996 KB Output is correct
18 Correct 95 ms 38964 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 152288 KB Output is correct
2 Correct 439 ms 152380 KB Output is correct
3 Correct 581 ms 159120 KB Output is correct
4 Correct 446 ms 172112 KB Output is correct
5 Correct 212 ms 143696 KB Output is correct
6 Correct 211 ms 143436 KB Output is correct
7 Correct 214 ms 143464 KB Output is correct
8 Correct 207 ms 143468 KB Output is correct
9 Correct 226 ms 159556 KB Output is correct
10 Correct 201 ms 143172 KB Output is correct
11 Correct 195 ms 142020 KB Output is correct
12 Correct 242 ms 142788 KB Output is correct
13 Correct 398 ms 145976 KB Output is correct
14 Correct 706 ms 154500 KB Output is correct
15 Correct 423 ms 150648 KB Output is correct
16 Correct 395 ms 150608 KB Output is correct
17 Correct 269 ms 145096 KB Output is correct
18 Correct 264 ms 145084 KB Output is correct