oj.uz

Submission #13396

# Submission time Handle Problem Language Result Execution time Memory
13396 2015-02-15T19:26:29 Z pseudopodia Jousting tournament (IOI12_tournament) C++
100 / 100
 128 ms 6232 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5088 KB Output is correct
2 Correct 0 ms 5088 KB Output is correct
3 Correct 0 ms 5088 KB Output is correct
4 Correct 1 ms 5088 KB Output is correct
5 Correct 0 ms 5088 KB Output is correct
6 Correct 0 ms 5088 KB Output is correct
7 Correct 0 ms 5088 KB Output is correct
8 Correct 0 ms 5088 KB Output is correct
9 Correct 0 ms 5088 KB Output is correct
10 Correct 0 ms 5088 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5088 KB Output is correct
2 Correct 6 ms 5088 KB Output is correct
3 Correct 0 ms 5088 KB Output is correct
4 Correct 5 ms 5088 KB Output is correct
5 Correct 5 ms 5088 KB Output is correct
6 Correct 4 ms 5088 KB Output is correct
7 Correct 6 ms 5088 KB Output is correct
8 Correct 6 ms 5088 KB Output is correct
9 Correct 0 ms 5088 KB Output is correct
10 Correct 3 ms 5088 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5532 KB Output is correct
2 Correct 125 ms 6232 KB Output is correct
3 Correct 13 ms 5480 KB Output is correct
4 Correct 127 ms 6232 KB Output is correct
5 Correct 121 ms 6196 KB Output is correct
6 Correct 100 ms 5968 KB Output is correct
7 Correct 127 ms 6232 KB Output is correct
8 Correct 128 ms 6232 KB Output is correct
9 Correct 13 ms 5480 KB Output is correct
10 Correct 12 ms 5480 KB Output is correct