oj.uz

Submission #761052

# Submission time Handle Problem Language Result Execution time Memory
761052 2023-06-19T06:51:12 Z NothingXD Jousting tournament (IOI12_tournament) C++17
100 / 100
 62 ms 19020 KB 
#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 H, typename... T>
void debug_out(H h, T... 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)

const int maxn = 1e5 + 10;
const int lg = 20;
const int inf = 1e9;
int n, a[maxn], val, f[maxn], par[maxn], dp[maxn << 1], mx[maxn << 1], l[maxn << 1], r[maxn << 1];
vector<int> g[maxn << 1];
pii ans = {0, -inf};
void add(int idx, int x){
	for (; idx <= n; idx += idx & -idx) f[idx] += x;
}

int find(int idx){
	int res = 0;
	for (int i = lg-1; ~i; i--){
		int ptr = res + (1 << i);
		if (ptr <= n && f[ptr] < idx){
			idx -= f[ptr];
			res = ptr;
		}
	}
	return res;
}

void dfs(int v){
	if (v < n){
		l[v] = r[v] = v;
		mx[v] = 0;
		return;
	}
	for (auto u: g[v]){
		dfs(u);
	}
	l[v] = l[g[v][0]];
	r[v] = r[g[v].back()];
	for (auto u: g[v]){
		mx[v] = max(mx[v], mx[u]);
		if (r[u] != r[v]) mx[v] = max(mx[v], a[r[u]]);
	}
}


void solve(int v, int p = -1){
	dp[v] = (p != -1? dp[p]: 0);
	if (v < n){
		ans = max(ans, MP(dp[v], -v));
		return;
	}
	if (mx[v] > val) dp[v] = 0;
	else dp[v]++;
	for (auto u: g[v]){
		solve(u, v);
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N;
	for (int i = 0; i < N; i++){
		par[i] = i;
		add(i+1, 1);
	}
	for (int i = 0; i < N-1; i++){
		a[i] = K[i];
	}
	val = R;
	for (int i = 0; i < C; i++){
		int idx = find(S[i] + 1);
		g[n+i].push_back(par[idx]);
		par[idx] = n+i;
		for (int j = S[i]+2; j <= E[i]+1; j++){
			int idx = find(S[i]+2);
			g[n+i].push_back(par[idx]);
			add(idx+1, -1);
		}
	}
	dfs(N+C-1);
	solve(N+C-1);
	return -ans.S;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 5076 KB Output is correct
4 Correct 2 ms 5076 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 2 ms 5076 KB Output is correct
8 Correct 2 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 2 ms 5052 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 5 ms 5716 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 4 ms 5460 KB Output is correct
5 Correct 4 ms 5460 KB Output is correct
6 Correct 4 ms 5300 KB Output is correct
7 Correct 4 ms 5612 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 5 ms 5460 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8340 KB Output is correct
2 Correct 62 ms 19020 KB Output is correct
3 Correct 25 ms 9596 KB Output is correct
4 Correct 49 ms 17160 KB Output is correct
5 Correct 47 ms 18076 KB Output is correct
6 Correct 48 ms 12864 KB Output is correct
7 Correct 51 ms 18392 KB Output is correct
8 Correct 59 ms 18360 KB Output is correct
9 Correct 23 ms 9108 KB Output is correct
10 Correct 24 ms 9536 KB Output is correct