Submission #946004

#	Time	Username	Problem	Language	Result	Execution time	Memory
946004		yhkhoo	Jousting tournament (IOI12_tournament)	C++17	100 / 100	586 ms	14932 KiB

tournament

// late knights in the middle of june...

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second

#define lsb(x) ((x) & (-x))

const int MAXN = 100005;
int fw1[MAXN];
int fw2[MAXN];
void update(int *fw, int X, int V){
	X++;
	while(X<MAXN){
		fw[X] += V;
		X += lsb(X);
	}
}
int query(int *fw, int R){
	R++;
	if(R==0) return 0;
	int result = 0;
	while(R){
		result += fw[R];
		R -= lsb(R);
	}
	return result;
}
int fbs(int *fw, int V){
	int pos=0;
	int cs=0;
	for(int x=16; x>=0; x--){
		if(pos+(1<<x) >= MAXN) continue;
		if(cs + fw[pos+(1<<x)] < V){
			pos += 1<<x;
			cs += fw[pos];
		}
	}
	return pos;
}

struct node{
	int s, e, m;
	int val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val = 0;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void update(int X, int V){
		if(s == X && e == X){
			val = V;
		}
		else{
			if(X <= m) l->update(X, V);
			else r->update(X, V);
			
			val = max(l->val, r->val);
		}
	}
	
	int query(int S, int E){
		if(s == S && e == E) return val;
		else if(E<=m) return l->query(S, E);
		else if(S>m) return r->query(S, E);
		else return max(l->query(S, m), r->query(m+1, E));
	}
} *root;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	cerr << '\n';
	memset(fw1, 0, sizeof(fw1));
	for(int i=1; i<=N; i++){
		update(fw1, i, 1);
	}
	pii q[C];
	/*for(int i=0; i<C; i++){
		int rs = fbs(fw1, S[i]);
		int re = fbs(fw1, E[i]+1)-1;
		q[i] = mp(rs, re);
		int ts;
		while((ts = fbs(fw1, rs+1)) <= re){
			update(fw1, ts, -1);
		}
		cerr << rs << ' ' << re << '\n';
	}*/
	vector<int> goat;
	goat.reserve(N+1);
	for(int i=0; i<=N; i++){
		goat.push_back(i);
	}
	for(int i=0; i<C; i++){
		int rs = goat[S[i]];
		int re = goat[E[i]+1]-1;
		/*cerr << rs << ' ' << re << '\n';
		for(auto j: goat){
			cerr << j << ' ';
		}
		cerr << '\n';*/
		q[i] = mp(rs, re);
		for(int j=S[i]+1; j<=E[i]; j++){
			goat.erase(goat.begin()+S[i]+1);
		}
	}
	root = new node(0, N-2);
	for(int i=0; i<N-1; i++){
		root->update(i, K[i]);
	}
	memset(fw2, 0, sizeof(fw2));
	for(int i=0; i<C; i++){
		int cmax = root->query(q[i].fi, q[i].se-1);
		if(cmax < R){
			update(fw2, q[i].fi, 1);
			update(fw2, q[i].se+1, -1);
		}
	}
	int cmax=0, P=0;
	for(int i=0; i<N; i++){
		int temp = query(fw2, i);
		/*int temp = 0;
		for(int j=0; j<C; j++){
			if(i >= q[j].fi && i <= q[j].se && root->query(q[j].fi, q[j].se-1) < R){
				temp++;
			}
		}*/
		cerr << temp << ' ';
		if(temp > cmax){
			cmax = temp;
			P = i;
		}
	}
	cerr << '\n';
	return P;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51