Submission #46166

#	Time	Username	Problem	Language	Result	Execution time	Memory
46166		mohammad_kilani	Jousting tournament (IOI12_tournament)	C++17	100 / 100	515 ms	46392 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int N = 300010 , LOG = 20;
int seg[4 * N] , n , dp[LOG][N] , root , low , high , res , mid , depth[N] , nxt[N] , pre[N]  , tmp , l , cnt = 0;
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 < pair<int,int> > st;
set < pair<int,int> > :: iterator it;

void DFS(int node,int prnt,int d){
	depth[node] = d;
	dp[0][node] = prnt;
	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 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(make_pair(i,i));
	cnt = n;
	for(int i=0;i<C;i++){
		S[i] = lob(S[i] + 1);
		E[i] = lob(E[i] + 1);
		it = st.lower_bound(make_pair(S[i],0));
		while(it != st.end() && it->first <= E[i]){
			g[cnt].push_back(it->second);
			g[it->second].push_back(cnt);
			if(it->first != S[i]) update(0,n-1,1,it->first);
			st.erase(it);
			it = st.lower_bound(make_pair(S[i],0));
		}
		st.insert(make_pair(S[i],cnt++));
	}
	it = st.lower_bound(make_pair(0,0));
	root = it->second;
	DFS(root,-1,0);
	for(int k=1;k<LOG;k++){
		for(int i=0;i<cnt;i++){
			if(dp[k-1][i] == -1)
				dp[k][i] = -1;
			else{
				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 = 0;
		if(pre[i] != -1){
			l = LCA(i,pre[i]);
			tmp = max(tmp,depth[l]);
		}
		if(nxt[i] != n - 1){
			l = LCA(i,nxt[i] + 1);
			tmp = max(tmp,depth[l]);
		}
		if(depth[i] - tmp - 1> mx){
			mx = depth[i] - tmp - 1;
			bestidx = i;
		}
	}
  	return bestidx;
}

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