Submission #46145

#	Time	Username	Problem	Language	Result	Execution time	Memory
46145		mohammad_kilani	Jousting tournament (IOI12_tournament)	C++17	0 / 100	248 ms	15560 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int N = 100010 , LOG = 19;
int seg[4 * N] , n , dp[LOG][N] , dp2[LOG][N] , root , low , high , res , mid , depth[N] , nxt[N] , pre[N] , cur[N] , tmp , l;
vector< int > g[N] ;  
int build(int s,int e,int idx){
	if(s == e) return seg[idx] = 1;
	return seg[idx] = build(s,(s+e)/2,idx*2) + build((s+e)/2+1,e,idx*2+1);
}

int getsum(int s,int e,int idx,int l,int r){
	if(s > r || e < l) return 0;
	if(s >= l && e <= r) return seg[idx];
	return getsum(s,(s+e)/2,idx*2,l,r) + getsum((s+e)/2+1,e,idx*2+1,l,r);
}

int update(int s,int e,int idx,int idx2){
	if(s > idx2 || e < idx2) return seg[idx];
	if(s == e) return seg[idx] = 0;
	return seg[idx] = update(s,(s+e)/2,idx*2,idx2) + update((s+e)/2+1,e,idx*2+1,idx2);
}

int lob(int val){
	low = 0 , high = n - 1 , res = n;
	while(high >= low){
		mid = (low + high) / 2;
		if(getsum(0,n-1,1,0,mid) >= val){
			res = mid;
			high = mid - 1;
		}
		else
			low = mid + 1;
	}
	return res;
}

set < int > st;
set < int > :: iterator it;

void DFS(int node,int prnt,int d){
	depth[node] = d;
	dp[0][node] = prnt;
	dp2[0][node] = cur[node];
	for(int i=0;i<(int)g[node].size();i++){
		if(g[node][i] != prnt)
			DFS(g[node][i],node,d + 1);
	}
}

int LCA(int u,int v){
	if(depth[u] > depth[v])
		swap(u,v);
	for(int k=LOG-1;k>=0;k--){
		if(depth[u] - (1 << k) >= depth[v]){
			u = dp[k][u];
		}
	}
	if(u == v)
		return u;
	for(int k=LOG-1;k>=0;k--){
		if(dp[k][u] != dp[k][v]){
			u = dp[k][u];
			v = dp[k][v];
		}
	}
	return dp[0][u];
}

int get(int u,int v){
	int s = 0;
	for(int k=LOG-1;k>=0;k--){
		if(depth[u] - (1 << k) >= depth[v]){
			s += dp2[k][v];
			v = dp[k][v];
		}
	}
	return s;
}

int GetBestPosition(int nnnn, int C, int R, int *K, int *S, int *E) {
	n = nnnn;
	build(0,n-1,1);
	for(int i=0;i<n;i++)
		st.insert(i);
	for(int i=0;i<C;i++){
		S[i] = lob(S[i] + 1);
		E[i] = lob(E[i] + 1);
		cur[S[i]]++;
		it = st.upper_bound(S[i]);
		while(it != st.end() && *it <= E[i]){
			g[*it].push_back(S[i]);
			g[S[i]].push_back(*it);
			update(0,n-1,1,*it);
			st.erase(it);
			it = st.upper_bound(S[i]);
		}
	}
	assert(st.size() == 1);
	it = st.lower_bound(0);
	root = *it;
	DFS(root,-1,0);
	for(int k=1;k<LOG;k++){
		for(int i=1;i<=n;i++){
			if(dp[k-1][i] == -1)
				dp[k][i] = -1;
			else{
				dp2[k][i] = dp2[k-1][i] + dp2[k-1][dp[k-1][i]];
				dp[k][i] = dp[k-1][dp[k-1][i]];
			}
		}
	}
	pre[0] = -1;
	for(int i=1;i<n-1;i++){
		if(K[i-1] > R)
			pre[i] = i - 1;
		else
			pre[i] = pre[i-1];
	}
	nxt[n-1] = n - 1;
	for(int i=n-2;i>=0;i--){
		if(K[i] > R)
			nxt[i] = i;
		else
			nxt[i] = nxt[i + 1];
	}
	int bestidx = 0 ,mx = -1;
	for(int i=0;i<n-1;i++){
		tmp = get(i,root) + cur[root];
		if(pre[i] != -1){
			l = LCA(i,pre[i]);
			tmp = min(tmp,get(i,l));
		}
		if(nxt[i] != n - 1){
			l = LCA(i,nxt[i] + 1);
			tmp  = min(tmp,get(i,l));
		}
		if(tmp > mx){
			mx = tmp;
			bestidx = i;
		}
	}
  	return bestidx;
}

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