oj.uz

Submission #1089982

# Submission time Handle Problem Language Result Execution time Memory
1089982 2024-09-17T13:36:29 Z Tob Teams (IOI15_teams) C++14
0 / 100
 609 ms 172108 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[]) {
	vector <int> dp(m+1, 0), wh(m, -1);
	set <pii> s;
	set <int> p;
	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});
				if (dp[x+1] <= dp[z+1]) s.insert({(wh[x]=-1), x});
				else {
					pii p2 = get(root[K[x]], root[K[z]], K[i], N-1, dp[x+1]-dp[z+1]);
					if (p2.F == -1) s.insert({wh[x]=N-1, x});
					else s.insert({wh[x]=p2.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[i+1] == dp[z+1]) s.insert({wh[z]=-1, z});
			else {
				pii p3 = get(root[K[z]], root[K[i]], K[i], N-1, dp[z+1]-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);
	}
	return (dp[m] >= 0);
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Incorrect 5 ms 12124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 39752 KB Output is correct
2 Correct 53 ms 39764 KB Output is correct
3 Correct 50 ms 39508 KB Output is correct
4 Correct 96 ms 50516 KB Output is correct
5 Incorrect 30 ms 38224 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 40528 KB Output is correct
2 Correct 110 ms 40492 KB Output is correct
3 Correct 123 ms 43700 KB Output is correct
4 Correct 92 ms 50512 KB Output is correct
5 Incorrect 69 ms 38992 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 152292 KB Output is correct
2 Correct 481 ms 152464 KB Output is correct
3 Correct 609 ms 159156 KB Output is correct
4 Correct 448 ms 172108 KB Output is correct
5 Incorrect 201 ms 143700 KB Output isn't correct
6 Halted 0 ms 0 KB -