oj.uz

Submission #280456

# Submission time Handle Problem Language Result Execution time Memory
280456 2020-08-22T19:30:38 Z amiratou Jousting tournament (IOI12_tournament) C++14
17 / 100
 1000 ms 2176 KB 
#include <bits/stdc++.h>
using namespace std;

int fen[100005],init[100005],nxt[100005],pr[100005],KK[100005],n;
void update(int idx,int val){
	for (int i = idx; i <= (n+1); i+=(i&(-i)))
		fen[i]+=val;
}
int get(int idx){
	int h=0;
	for (int i = idx; i >= 1; i-=(i&(-i)))
		h+=fen[i];
	return h;
}
int gimme(int nb,int l=0,int r=n){
	nb++;
	int ans=-1;
	while(l<=r){
		int med=(l+r)>>1;
		if(get(med+1)>=nb)
			r=med-1,ans=med;
		else l=med+1;
	}
	assert(ans!=-1);
	return ans;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	vector<int> vec(N);
	n=N;
	for (int i = 1; i <= N; ++i)
		update(i,1),vec[i-1]=K[i-1];
	update(N+1,1);
	for (int i = 1; i <= N+1; ++i)init[i]=fen[i];
	int ans=-1,m=-1;
	for (int p = 0; p <= N; ++p)
	{
		int sum=0;
		for (int i = 1; i <= N+1; ++i){
			if((i-1)<p)KK[i-1]=K[i-1];
			else if((i-1)==p)KK[i-1]=R;
			else KK[i-1]=K[i-2];
			fen[i]=init[i];
			if(i!=1)pr[i-1]=i-2;
			if(i!=(N+1))nxt[i-1]=i;
		}
		vec.insert(vec.begin()+p,R);
		for (int i = 0; i < C; ++i)
		{
			int st=gimme(S[i]),e=gimme(E[i]);
			int ST=st;
			int maxi=-1,arg=-1;
			while(st!=e){
				if(KK[st]>maxi)maxi=KK[st],arg=st;
				update(st+1,-1);
				st=nxt[st];
			}
			if(KK[e]>maxi)maxi=KK[e],arg=e;
			update(e+1,-1);
			update(arg+1,1);
			sum+=(arg==p);
			if(ST)nxt[pr[ST]]=arg,pr[arg]=pr[ST];
			if(e!=N)nxt[arg]=nxt[e],pr[nxt[e]]=arg;
		}
		if(sum>ans)ans=sum,m=p;
		vec.erase(vec.begin()+p);
	}
	return m;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 53 ms 384 KB Output is correct
4 Correct 43 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 47 ms 384 KB Output is correct
7 Correct 46 ms 384 KB Output is correct
8 Correct 48 ms 404 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 12 ms 384 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 416 KB Output is correct
2 Execution timed out 1080 ms 640 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 2176 KB Time limit exceeded
2 Halted 0 ms 0 KB -