oj.uz

Submission #805269

# Submission time Handle Problem Language Result Execution time Memory
805269 2023-08-03T14:41:10 Z NothingXD Teams (IOI15_teams) C++17
100 / 100
 2787 ms 163336 KB 
#include "teams.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 5e5 + 10;
const int lg = 22;
const int inf = 1e9;

int n, a[maxn], b[maxn], seg[maxn*lg], lc[maxn*lg], rc[maxn*lg], root[maxn], vercnt = 1;
vector<int> val[maxn];

void build(int v, int l, int r){
	if (l + 1 == r){
		return;
	}
	lc[v] = vercnt++;
	rc[v] = vercnt++;
	int mid = (l + r) >> 1;
	build(lc[v], l, mid);
	build(rc[v], mid, r);
}

void add(int v, int newv, int l, int r, int idx){
	if (l + 1 == r){
		seg[newv] = seg[v] + 1;
		return;
	}
	int mid = (l + r) >> 1;
	if (idx < mid){
		lc[newv] = vercnt++;
		rc[newv] = rc[v];
		add(lc[v], lc[newv], l, mid, idx);
	}
	else{
		lc[newv] = lc[v];
		rc[newv] = vercnt++;
		add(rc[v], rc[newv], mid, r, idx);
	}
	seg[newv] = seg[lc[newv]] + seg[rc[newv]];
}

int get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return 0;
	if (ql <= l && r <= qr) return seg[v];
	int mid = (l + r) >> 1;
	return get(lc[v], l, mid, ql, qr)
		+ get(rc[v], mid, r, ql, qr);
}

void init(int N, int A[], int B[]){
	n = N;
	for (int i = 0; i < n; i++){
		val[A[i]].push_back(B[i]);
	}
	root[0] = 0;
	build(0, 1, n+1);
	for (int i = 1; i <= n; i++){
		root[i] = root[i-1];
		for (auto x: val[i]){
			int tmp = vercnt++;
			add(root[i], tmp, 1, n+1, x);
			root[i] = tmp;
		}
	}
}

int k[maxn], dp[maxn], func[maxn << 2];

int f(int idx, int x){
//	debug(idx, x, dp[idx], get(root[x], 1, n+1, x, n+1), get(root[k[idx]], 1, n+1, x, n+1));
	if (k[idx] > x) return -inf - idx;
	return dp[idx] + get(root[x], 1, n+1, x, n+1) - get(root[k[idx]], 1, n+1, x, n+1);
}

vector<int> del;
bool mark[maxn << 2];
void addfunc(int v, int l, int r, int idx){
//	debug(v, l, r, idx);
	if (!mark[v]){
		mark[v] = true;
		del.push_back(v);
	}
	int mid = (l + r) >> 1;
	bool L = f(idx, l) < f(func[v], l);
	bool M = f(idx, mid) < f(func[v], mid);
	if (M){
		swap(func[v], idx);
	}
//	debug(func[v]);
	if (l + 1 == r) return;
	if (L != M){
		addfunc(v << 1, l, mid, idx);
	}
	else{
		addfunc(v << 1 | 1, mid, r, idx);
	}
}

int getmin(int v, int l, int r, int idx){
	if (l + 1 == r) return f(func[v], idx);
	int mid = (l + r) >> 1;
	if (idx < mid) return min(f(func[v], idx), getmin(v << 1, l, mid, idx));
	else return min(f(func[v], idx), getmin(v << 1 | 1, mid, r, idx));
}

int can(int M, int K[]) {
	for (auto x: del){
		func[x] = 0;
		mark[x] = false;
	}
	del.clear();
	sort(K, K+M);
	for (int i = 1; i <= M; i++){
		k[i] = K[i-1];
	}
	dp[0] = 0;
	for (int i = 1; i <= M; i++){
		dp[i] = getmin(1, 1, n+1, k[i]) - k[i];
//		debug(i, dp[i]);
		if (dp[i] < 0) return 0;
		addfunc(1, 1, n+1, i);
	}
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 6 ms 12088 KB Output is correct
4 Correct 6 ms 12028 KB Output is correct
5 Correct 5 ms 12116 KB Output is correct
6 Correct 6 ms 12144 KB Output is correct
7 Correct 8 ms 12128 KB Output is correct
8 Correct 10 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 11 ms 12116 KB Output is correct
13 Correct 11 ms 12128 KB Output is correct
14 Correct 7 ms 12116 KB Output is correct
15 Correct 6 ms 12116 KB Output is correct
16 Correct 6 ms 12116 KB Output is correct
17 Correct 6 ms 12116 KB Output is correct
18 Correct 6 ms 11988 KB Output is correct
19 Correct 6 ms 11988 KB Output is correct
20 Correct 6 ms 12116 KB Output is correct
21 Correct 7 ms 12160 KB Output is correct
22 Correct 7 ms 12116 KB Output is correct
23 Correct 6 ms 12116 KB Output is correct
24 Correct 6 ms 12116 KB Output is correct
25 Correct 6 ms 11988 KB Output is correct
26 Correct 6 ms 12116 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 37416 KB Output is correct
2 Correct 57 ms 37444 KB Output is correct
3 Correct 50 ms 37324 KB Output is correct
4 Correct 51 ms 38160 KB Output is correct
5 Correct 30 ms 36392 KB Output is correct
6 Correct 28 ms 36268 KB Output is correct
7 Correct 27 ms 36284 KB Output is correct
8 Correct 27 ms 36308 KB Output is correct
9 Correct 302 ms 36780 KB Output is correct
10 Correct 143 ms 35464 KB Output is correct
11 Correct 46 ms 36512 KB Output is correct
12 Correct 28 ms 36544 KB Output is correct
13 Correct 36 ms 35708 KB Output is correct
14 Correct 37 ms 36804 KB Output is correct
15 Correct 51 ms 37376 KB Output is correct
16 Correct 46 ms 37224 KB Output is correct
17 Correct 30 ms 36560 KB Output is correct
18 Correct 32 ms 36692 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 37884 KB Output is correct
2 Correct 60 ms 37992 KB Output is correct
3 Correct 665 ms 40812 KB Output is correct
4 Correct 56 ms 38220 KB Output is correct
5 Correct 707 ms 36768 KB Output is correct
6 Correct 623 ms 36676 KB Output is correct
7 Correct 36 ms 36684 KB Output is correct
8 Correct 452 ms 36724 KB Output is correct
9 Correct 334 ms 36804 KB Output is correct
10 Correct 665 ms 35672 KB Output is correct
11 Correct 813 ms 36820 KB Output is correct
12 Correct 861 ms 36880 KB Output is correct
13 Correct 950 ms 36272 KB Output is correct
14 Correct 821 ms 39696 KB Output is correct
15 Correct 689 ms 37964 KB Output is correct
16 Correct 687 ms 37932 KB Output is correct
17 Correct 644 ms 37212 KB Output is correct
18 Correct 659 ms 37036 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 152864 KB Output is correct
2 Correct 455 ms 152900 KB Output is correct
3 Correct 2160 ms 158748 KB Output is correct
4 Correct 450 ms 160588 KB Output is correct
5 Correct 1801 ms 151504 KB Output is correct
6 Correct 1581 ms 151500 KB Output is correct
7 Correct 124 ms 151432 KB Output is correct
8 Correct 1307 ms 151476 KB Output is correct
9 Correct 1914 ms 152040 KB Output is correct
10 Correct 1924 ms 149148 KB Output is correct
11 Correct 2067 ms 149848 KB Output is correct
12 Correct 2256 ms 150708 KB Output is correct
13 Correct 2787 ms 154428 KB Output is correct
14 Correct 2529 ms 163336 KB Output is correct
15 Correct 1901 ms 158928 KB Output is correct
16 Correct 1931 ms 158892 KB Output is correct
17 Correct 1682 ms 153428 KB Output is correct
18 Correct 1715 ms 153368 KB Output is correct