oj.uz

Submission #4656

# Submission time Handle Problem Language Result Execution time Memory
4656 2013-11-16T09:09:47 Z cki86201 Jousting tournament (IOI12_tournament) C++
0 / 100
 20 ms 2944 KB 
#include<algorithm>
using namespace std;

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

void update(int a,int b,int item)
{
	a+=idx,b+=idx;
	while(a<=b){
		if(a&1)T[a]+=item;
		if((b&1)==0)T[b]+=item;
		a=(a+1)>>1, b=(b-1)>>1;
	}
}

int read1(int x)
{
	int ret=0;
	x+=idx;
	while(x)ret+=T[x],x>>=1;
	return ret;
}

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 GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	int i;
	for(i=0;i<C;i++){
		int s = read1(S[i]-1) + S[i];
		int e = read1(E[i]) + E[i];
		update(s,N-1,E[i]-S[i]);
		S[i]=s,E[i]=e;
	}
	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
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2500 KB Output is correct
2 Incorrect 0 ms 2500 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 2500 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 20 ms 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -