oj.uz

Submission #4657

# Submission time Handle Problem Language Result Execution time Memory
4657 2013-11-16T14:28:32 Z cki86201 Jousting tournament (IOI12_tournament) C++
100 / 100
 44 ms 4036 KB 
#include<algorithm>
using namespace std;

const int idx = 1<<17;
int T[1<<18];

void update(int a){a+=idx;while(a)T[a]--,a>>=1;}

int read1(int x)
{
	if(x==-1)return -1;
	int a=1;
	while(a<idx){
		if(T[2*a]<x)x-=T[2*a],a=2*a+1;
		else a=2*a;
	}
	return a-idx;
}

int read2(int a,int b)
{
	a+=idx,b+=idx;
	int ret = 0;
	while(a<=b){
		ret=max(ret,T[a]);
		ret=max(ret,T[b]);
		a = (a+1)>>1, b = (b-1)>>1;
	}
	return ret;
}

int sum[100010],ans;
int d[100010];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	int i;
	for(i=0;i<N;i++)d[i]=i+1,T[i+idx]=1;
	for(i=idx-1;i;i--)T[i]=T[i<<1] + T[i<<1|1];
	for(i=0;i<C;i++){
		int a = read1(S[i]+1);
		int tmp = a;
		for(int j=0;j<E[i]-S[i];j++){
			tmp = d[tmp];
			update(tmp);
		}
		d[a] = d[tmp];
		E[i] = d[tmp]-1;
		S[i] = a;
	}
	for(i=0;i<N-1;i++)T[i+idx]=K[i];
	for(i=idx-1;i;i--)T[i]=max(T[i<<1],T[i<<1|1]);
	for(i=0;i<C;i++){
		int s = read2(S[i],E[i]-1);
		if(s<R)sum[S[i]]++,sum[E[i]+1]--;
	}
	for(i=0;i<N;i++)sum[i]+=sum[i-1];
	for(i=0;i<N;i++)if(sum[ans]<sum[i])ans=i;
	return ans;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3336 KB Output is correct
2 Correct 44 ms 4036 KB Output is correct
3 Correct 12 ms 3284 KB Output is correct
4 Correct 44 ms 4036 KB Output is correct
5 Correct 44 ms 4000 KB Output is correct
6 Correct 36 ms 3772 KB Output is correct
7 Correct 44 ms 4036 KB Output is correct
8 Correct 44 ms 4036 KB Output is correct
9 Correct 8 ms 3284 KB Output is correct
10 Correct 12 ms 3284 KB Output is correct