oj.uz

Submission #13395

# Submission time Handle Problem Language Result Execution time Memory
13395 2015-02-15T18:58:37 Z pseudopodia Jousting tournament (IOI12_tournament) C++
0 / 100
 41 ms 7096 KB 
#include <stdio.h>
#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<<2];

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], ed = E[r]-1;
		kill(1,0,bin-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
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6652 KB Output is correct
2 Incorrect 0 ms 6652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 7096 KB Output isn't correct
2 Halted 0 ms 0 KB -