Submission #13396

#	Time	Username	Problem	Language	Result	Execution time	Memory
13396		pseudopodia	Jousting tournament (IOI12_tournament)	C++98	100 / 100	128 ms	6232 KiB

tournament

#include <algorithm>
#define maxN 100010
#define maxBinN 131072
#define MAX(a,b) ((a>b)?a:b)
#define MIN(a,b) ((a<b)?a:b)
using namespace std;

int it[maxBinN<<1], bin;
int alive[maxBinN<<1];

struct Layer{
	int add, i;
	inline bool operator < (const Layer &c) const{
		return i < c.i;
	}
}wins[maxN<<1];

int renumber(int x, int s, int e, int remain)
{
	int m = (s+e)>>1;
	if( x>=bin ) return m;
	if( alive[x<<1] >= remain ) return renumber(x<<1,s,m,remain);
	return renumber(x<<1|1,m+1,e,remain-alive[x<<1]);
}

int st, ed;
void kill(int x, int s, int e)
{
	if( e<st || ed<s ) return;
	else if( st<=s && e<=ed ) alive[x] = 0;
	else
	{
		int m = (s+e)>>1;
		kill(x<<1,s,m);
		kill(x<<1|1,m+1,e);
		alive[x] = MIN( alive[x<<1]+alive[x<<1|1], alive[x] );
	}
}

int getMax(int x, int s, int e)
{
	if( e<st || ed<s ) return -1;
	else if( st<=s && e<=ed ) return it[x];
	else
	{
		int m = (s+e)>>1, t, tt;
		t = getMax(x<<1,s,m);
		tt = getMax(x<<1|1,m+1,e);
		return MAX(t,tt);
	}
}

int ee[maxN];
int GetBestPosition(int n, int rn, int my, int *a, int *S, int *E)
{
	bin = 1;
	while( n > bin ) bin<<=1;
	for(int i=0;i<n-1;i++) it[bin+i] = a[i];
	for(int i=0;i<n;i++) alive[bin+i] = 1, ee[i] = i;
	for(int i=bin-1;i;i--)
	{
		it[i] = MAX(it[i<<1],it[i<<1|1]);
		alive[i] = alive[i<<1] + alive[i<<1|1];
	}

	int m = 0;
	for(int r=0;r<rn;r++)
	{
		S[r] = renumber(1,0,bin-1,S[r]+1);
		E[r] = renumber(1,0,bin-1,E[r]+1);
		ee[S[r]] = E[r] = ee[E[r]];

		st = S[r]+1, ed = E[r];
		kill(1,0,bin-1);
		
		st = S[r], ed = E[r]-1;
		if( my > getMax(1,0,bin-1) )
		{
			wins[m].i = S[r], wins[m++].add = 1;
			wins[m].i = E[r], wins[m++].add = -1;
		}
	}

	int acc = 0, best = 0, ans = 0;
	sort(wins,wins+m);
	for(int i=0;i<m;i++)
	{
		acc += wins[i].add;
		if( acc > best ) best = acc, ans = wins[i].i;
	}

	return ans;
}

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