Submission #406328

#	Time	Username	Problem	Language	Result	Execution time	Memory
406328		ritul_kr_singh	Jousting tournament (IOI12_tournament)	C++17	100 / 100	123 ms	24428 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N){ a.resize((n=N)+1); }
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		for(s=0; i>=1; i-=i&-i) s += a[i];
		return s;
	}
	int get(int l, int r){ return get(r+1) - get(l); }
	int lower(int v){
		int i = 0;
		for(s=1<<20; s; s/=2) if(i+s<=n && a[i+s]<v) v -= a[i+=s];
		return i;
	}
};

const int MAXN = 2e5;

struct SegmentTree{
	vector<int> a; int sz = 1;
	void init(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.assign(2*sz, -1);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx < (int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx + rx) / 2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	int rangeMax(int l, int r, int x, int lx, int rx){
		if(r<=lx || rx<=l) return -1;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return max(rangeMax(l, r, 2*x+1, lx, mx), rangeMax(l, r, 2*x+2, mx, rx));
	}
	int rangeMax(int l, int r){ return rangeMax(l, r+1, 0, 0, sz); }
};


vector<int> g[MAXN];
int low[MAXN], high[MAXN], lim;
array<int, 2> dist[MAXN];
array<int, 2> ans = {0, 0};

SegmentTree st;

void dfs(int u){
	if(g[u].empty()){
		low[u] = high[u] = u;
		dist[u] = {0, -u};
	}else low[u] = MAXN * 3, high[u] = -1;

	for(int v : g[u]){
		dfs(v);
		low[u] = min(low[u], low[v]);
		high[u] = max(high[u], high[v]);
		++dist[v][0];
		dist[u] = max(dist[u], dist[v]);
	}

	int m = st.rangeMax(low[u], high[u] - 1);
	if(m <= lim) ans = max(ans, dist[u]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	FenwickTree f(N);
	lim = R;
	for(int i=0; i<N; ++i) f.add(i, 1);

	int a[N]; iota(a, a+N, 0LL);
	int curr = N - 1;

	for(int i=0; i<C; ++i){
		++curr;
		int l = f.lower(S[i] + 1), num = E[i] - S[i] + 1;
		g[curr].push_back(a[l]);
		a[l] = curr;
		for(int j=1; j<num; ++j){
			int k = f.lower(S[i] + 2);
			g[curr].push_back(a[k]);
			f.add(k, -1);
		}
	}

	vector<int> v(N-1);
	for(int i=0; i<N-1; ++i) v[i] = K[i];
	st.init(v);

	dfs(curr);

	return -ans[1];
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51