Submission #132292

#	Time	Username	Problem	Language	Result	Execution time	Memory
132292		Lawliet	Jousting tournament (IOI12_tournament)	C++14	0 / 100	106 ms	12960 KiB

tournament

#include <bits/stdc++.h>

#define LOG 20
#define MAX 100010

using namespace std;
typedef pair<int,int> pii;

class SegmentTree
{
	public:
		
		int getLeft(int i) { return 2*i; }
		int getRight(int i) { return 2*i + 1; }
		
		void build(int node, int l, int r)
		{
			lazy[node] = -1;
			
			if(l == r) return void( sum[node] = 1 );
			
			int m = (l + r)/2;
			
			build(getLeft(node) , l , m);
			build(getRight(node) , m + 1 , r);
			
			sum[node] = sum[ getLeft(node) ] + sum[ getRight(node) ];
		}
		
		void refresh(int node, int l, int r)
		{
			if(lazy[node] == -1) return;
			
			int lz = lazy[node];
			lazy[node] = -1;
			
			sum[node] = lz*(r - l + 1);
			
			if(l == r) return;
			
			lazy[ getLeft(node) ] = lz;
			lazy[ getRight(node) ] = lz; 
		}
		
		void update(int node, int l, int r, int i, int j, int v)
		{
			refresh(node , l , r);
			
			if(j < l || r < i) return;
			if(i <= l && r <= j)
			{
				lazy[node] = v;
				
				refresh(node , l , r);
				
				return;
			}
			
			int m = (l + r)/2;
			
			update(getLeft(node) , l , m , i , j , v);
			update(getRight(node) , m + 1 , r , i , j , v);
			
			sum[node] = sum[ getLeft(node) ] + sum[ getRight(node) ];
		}
		
		int bs(int node, int l, int r, int k)
		{
			refresh(node , l , r);
			
			if(l == r) return l;
			
			int m = (l + r)/2;
			
			int sumLeft = sum[ getLeft(node) ];
			
			if(sumLeft >= k) return bs(getLeft(node) , l , m , k);
			return bs(getRight(node) , m + 1 , r , k - sumLeft);
		}
		
	private:
		
		int sum[4*MAX];
		int lazy[4*MAX];
};

int n, c, r;

int v[MAX];
int L[MAX];
int R[MAX];
int dp[LOG][MAX];
int nearestLeft[MAX];
int nearestRight[MAX];

pii interval[2*MAX];

set<pii> activedIntervals;
set<pii>::iterator it;

SegmentTree SEG;

void buildTree()
{
	SEG.build(1 , 1 , n);
	
	for(int g = 1 ; g <= n ; g++)
	{
		interval[g] = {g , g};
		
		activedIntervals.insert({g , g});
	}
	
	int curInterval = n;
		
	for(int g = 1 ; g <= c ; g++)
	{
		int newL = SEG.bs(1 , 1 , n , L[g]);
		int newR = SEG.bs(1 , 1 , n , R[g]);
						
		interval[ ++curInterval ] = {newL , newR};
		
		it = activedIntervals.lower_bound({newL , 0});
		vector<pii> aux;
		
		for( ; it->first <= newR && it != activedIntervals.end() ; it++)
		{
			dp[0][ it->second ] = curInterval;
			aux.push_back( *it );	
		}
			
		while( !aux.empty() )
		{
			activedIntervals.erase( aux.back() );
			aux.pop_back();	
		}	
		
		activedIntervals.insert({newL , curInterval});
		
		SEG.update(1 , 1 , n , newL , newR , 0);
		SEG.update(1 , 1 , n , newL , newL , 1);
	}
	
	dp[0][ curInterval ] = 0;
	
	for(int k = 1 ; k < LOG ; k++)
	{
		for(int g = 1 ; g <= curInterval ; g++)
		{
			int jump = dp[k - 1][g];
			dp[k][g] = dp[k - 1][jump];
		}
	}
}

int distLCA(int i, int j)
{
	int dist = 0;
	
	for(int k = LOG - 1 ; k >= 0 ; k--)
	{
		int jump = dp[k][j];
				
		if(jump == 0) continue;
		
		if(interval[jump].first > i || i > interval[jump].second)
		{
			j = jump;
			dist += (1 << k);
		}
	}
	
	return dist;
}

int GetBestPosition(int N, int C, int ranking, int *K, int *S, int *E)
{
	n = N; c = C; r = ranking;
	
	for(int g = 1 ; g <= C ; g++)
	{
		L[g] = S[g - 1] + 1;
		R[g] = E[g - 1] + 1;
	}
		
	for(int g = 1 ; g <= N ; g++)
		v[g] = K[g - 1];
		
	buildTree();
		
	nearestLeft[1] = -1;
	nearestRight[n] = -1;
	
	for(int g = 2 ; g <= n ; g++)
	{
		if(v[g - 1] > ranking) nearestLeft[g] = g - 1;
		else nearestLeft[g] = nearestLeft[g - 1];
	}
	
	for(int g = n - 1 ; g >= 1 ; g--)
	{
		if(v[g] > ranking) nearestRight[g] = g + 1;
		else nearestRight[g] = nearestRight[g + 1];
	}
	
	int qtdCombats = -1;
	int bestPosition;
	
	for(int g = 1 ; g <= n ; g++)
	{
		int ansLeft = distLCA(nearestLeft[g] , g);
		int ansRight = distLCA(nearestRight[g] , g);
		
		int ans = min(ansLeft , ansRight);
		
		if(ans > qtdCombats)
		{
			qtdCombats = ans;
			bestPosition = g;
		}	
	}
	
	return bestPosition;
}

/*int main()
{
	int nn, cc, rr;
	
	scanf("%d %d %d",&nn,&cc,&rr);
	
	int kk[nn], ss[cc + 1], ee[cc + 1];
	
	for(int g = 0 ; g < nn - 1 ; g++)
		scanf("%d",&kk[g]);
		
	for(int g = 0 ; g < cc ; g++)
		scanf("%d %d",&ss[g],&ee[g]);
		
	printf("%d\n",GetBestPosition(nn , cc , rr , kk , ss , ee));
}*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:223:9: warning: 'bestPosition' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return bestPosition;
         ^~~~~~~~~~~~

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