oj.uz

Submission #46166

# Submission time Handle Problem Language Result Execution time Memory
46166 2018-04-17T11:40:26 Z mohammad_kilani Jousting tournament (IOI12_tournament) C++17
100 / 100
 515 ms 46392 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7544 KB Output is correct
2 Correct 8 ms 7620 KB Output is correct
3 Correct 9 ms 7856 KB Output is correct
4 Correct 10 ms 7856 KB Output is correct
5 Correct 8 ms 7856 KB Output is correct
6 Correct 9 ms 7968 KB Output is correct
7 Correct 9 ms 7996 KB Output is correct
8 Correct 9 ms 7996 KB Output is correct
9 Correct 8 ms 7996 KB Output is correct
10 Correct 9 ms 7996 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8160 KB Output is correct
2 Correct 26 ms 9576 KB Output is correct
3 Correct 13 ms 9576 KB Output is correct
4 Correct 25 ms 9576 KB Output is correct
5 Correct 24 ms 9576 KB Output is correct
6 Correct 28 ms 9576 KB Output is correct
7 Correct 30 ms 9956 KB Output is correct
8 Correct 25 ms 9956 KB Output is correct
9 Correct 12 ms 9956 KB Output is correct
10 Correct 31 ms 9956 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 19528 KB Output is correct
2 Correct 515 ms 39740 KB Output is correct
3 Correct 142 ms 39740 KB Output is correct
4 Correct 461 ms 39740 KB Output is correct
5 Correct 490 ms 41000 KB Output is correct
6 Correct 498 ms 41000 KB Output is correct
7 Correct 464 ms 44728 KB Output is correct
8 Correct 493 ms 46392 KB Output is correct
9 Correct 105 ms 46392 KB Output is correct
10 Correct 188 ms 46392 KB Output is correct