Submission #289667

#	Time	Username	Problem	Language	Result	Execution time	Memory
289667		b00n0rp	Jousting tournament (IOI12_tournament)	C++17	49 / 100	1097 ms	2296 KiB

tournament

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

#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)

const int MAXN = 100005;

int n;
int lft[MAXN],rgt[MAXN];
int seg[MAXN*4];

void build(int ind,int l,int r){
	if(l == r){
		seg[ind] = 1;
		return;
	}
	int mid = (l+r)/2;
	build(2*ind,l,mid);
	build(2*ind+1,mid+1,r);
	seg[ind] = seg[2*ind]+seg[2*ind+1];
}

int quer(int ind,int l,int r,int val){ // returns first index such that pref[0..ind] >= val;
	if(l == r){
		if(seg[ind] == val) return l;
		else return l+1;
	}
	int mid = (l+r)/2;
	if(seg[2*ind] >= val) return quer(2*ind,l,mid,val);
	else return quer(2*ind+1,mid+1,r,val-seg[2*ind]);
}

void upd(int ind,int l,int r,int pos,int val){
	if(r < pos or l > pos) return;
	if(l == r){
		seg[ind] = val;
		return;
	}
	int mid = (l+r)/2;
	upd(2*ind,l,mid,pos,val);
	upd(2*ind+1,mid+1,r,pos,val);
	seg[ind] = seg[2*ind]+seg[2*ind+1];	
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	build(1,0,N-1);
	n = N;
	REP(i,C){
		vector<int> positions;
		FOR(j,S[i]+1,E[i]+3) positions.push_back(quer(1,0,N-1,j));
		positions.back()--;
		S[i] = positions[0];
		E[i] = positions.back();
		FOR(i,1,((int)positions.size())-1){
			// cout << "updating: " << positions[i] << endl;
			upd(1,0,N-1,positions[i],0);
		}
		// cout << S[i] << " " << E[i] << endl;
	}
	lft[0] = -1;
	rgt[n-1] = n-1;
	FOR(i,1,n) lft[i] = (K[i-1] > R)?(i-1):(lft[i-1]);
	for(int i = n-2; i >= 0; i--) rgt[i] = (K[i] > R)?(i):(rgt[i+1]);


	int pos = -1,mx = -1;
	REP(i,n){
		// cout << lft[i] << " " << rgt[i] << endl;
		int cnt = 0;
		REP(j,C){
			if(i >= S[j] and S[j] > lft[i] and i <= E[j] and E[j] <= rgt[i]) cnt++;
		}
		if(cnt > mx){
			mx = cnt;
			pos = i;
		}
	}
	return pos;
}

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