Submission #761047

#	Time	Username	Problem	Language	Result	Execution time	Memory
761047		NothingXD	Jousting tournament (IOI12_tournament)	C++17	0 / 100	26 ms	6556 KiB

tournament

#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;

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];
pii ans = {0, 0};
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: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51