Submission #593747

#	Time	Username	Problem	Language	Result	Execution time	Memory
593747		l_reho	Jousting tournament (IOI12_tournament)	C++14	0 / 100	14 ms	7508 KiB

tournament

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

struct info{
	
	int mx;
	bool marked;
	int sum;
	
	info(){}
	info(int _mx, bool _marked, int _sum): mx(_mx), marked(_marked), sum(_sum){}
	
};


vector<info> ST;
vector<int> V;
vector<int> alive;


void build(int p, int L, int R){
	if(L == R){
		
		ST[p].mx = L;
		ST[p].marked = 0;
		ST[p].sum = alive[L];
		
		return;
	}
	
	int mid = (L+R)/2;
	
	build(p*2, L, mid);
	build(p*2+1, mid+1, R);
	
	if(V[ST[p*2].mx] > V[ST[p*2+1].mx]) ST[p].mx = ST[p*2].mx;
	else ST[p].mx = ST[p*2+1].mx;
	
	ST[p].sum = ST[p*2].sum + ST[p*2+1].sum;
	
}

void push(int p, int L, int R){
	
	if(ST[p].marked == 0) return;
	
	if(L != R){
		ST[p*2].marked = 1;
		ST[p*2+1].marked = 1;
		
		ST[p*2].sum = 0;
		ST[p*2+1].sum = 0;
	}
	
	ST[p].marked = 0;
	ST[p].sum = 0;
	
}

int getMax(int p, int L, int R, int i, int j){
	
	push(p, L, R);
	
	if(i > R || j < L) return -1;
	
	if(i <= L && R <= j) return ST[p].mx;
	
	int mid = (L+R)/2;
	
	int idx1 = getMax(p*2, L, mid, i, j);
	int idx2 = getMax(p*2+1, mid+1, R, i, j);
	
	if(idx1 == -1) return idx2;
	if(idx2 == -1) return idx1;
	
	if(V[idx1] > V[idx2]) return idx1;
	
	return idx2;
	
}


int getIth(int pos, int N){
	
	int p = 1;
	int sum = 0;
	
	int low = 0;
	int high = N-1;
	int ret = -1;
	
	while(low < high){
		push(p, low, high);
		
		int mid = low + (high-low)/2;
		
		int sumLeft = ST[p*2].sum;
		
		
		if(sum + sumLeft >= pos){
			p*=2;
			high = mid;
			ret = mid;
		}else{
			sum += sumLeft;
			p = p*2+1;
			low = mid+1;
		}
	}
	
	return ret;
	
}

void update(int p, int L, int R, int i, int j){
	push(p, L, R);
	
	
	if(i > R || j < L) return;
	
	if(i <= L && R <= j){
		
		ST[p].sum = 0;
		
		if(L != R){
			ST[p*2].marked = 1;
			ST[p*2+1].marked = 1;
		}
		
		ST[p*2].marked = 0;
		
		return;
	}
	
		
	int mid = (L+R)/2;
	
	update(p*2, L, mid, i, j);
	update(p*2+1, mid+1, R, i, j);
	
	ST[p].sum = ST[p*2].sum + ST[p*2+1].sum; 
	
}



int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	
	ST.assign(N*4+1, {});
	V.assign(N, 0);
	alive.assign(N, 1);
	
	E[0]--;
	
	for(int i = 0; i < N; i++) V[i] = K[i];
	
	build(1, 0, N-1);
	
	unordered_map<int, int> mp;
	
	for(int c = 0; c < C; c++){
		int start = S[c]+1;
		int end = E[c]+1;
		
		// get startesimo e endesimo elemento
		int i = getIth(start, N);
		int j = getIth(end, N);
		
		// cerco il massimo 
		int mxIdx = getMax(1, 0, N-1, i, j);
		
		mp[V[mxIdx]]++;
		
		
		// cancello quelli attorno idx
		if(i <= mxIdx-1)
			update(1, 0, N-1, i, mxIdx-1);
		
		if(mxIdx+1 <= j)
			update(1, 0, N-1, mxIdx+1, j);
		
	}
	
	// cercare in mp il valore più piccolo di R che vince di più;
	
	int cnt = 0;
	
	for(auto m : mp){
		if(m.first < R)
			cnt = max(cnt, m.second);
	}
	
	
	return cnt;
}

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