Submission #217097

#	Time	Username	Problem	Language	Result	Execution time	Memory
217097		AQT	Jousting tournament (IOI12_tournament)	C++14	0 / 100	41 ms	7160 KiB

tournament

//#include <tournament.h>
#include <bits/stdc++.h>

using namespace std;

int N;
int bit[100005];
bool good[100005];
vector<int> lft[100005];
vector<int> rht[100005];
set<int> st;

void upd(int p, int v){
	for(int i = p; i<=N; i+=i&-i){
		bit[i] += v;
	}
}

int query(int p){
	int ret = 0;
	while(p){
		ret += bit[p];
		p -= p&-p;
	}
	return ret;
}

int clmb(int lim){
	int tot = 0;
	int p = 0;
	for(int b = 16; b>=0; b--){
		if((1<<b)+p <= N && tot + bit[(1<<b)+p] < lim){
			tot += bit[(1<<b)+p];
			p += (1<<b);
		}
	}
	return p+1;
}

int GetBestPosition(int NN, int Q, int K, int arr[], int L[], int R[]){
	N = NN;
	for(int i = 1; i<=N; i++){
		upd(i, 1);
	}
	for(int q = 0; q<Q; q++){
		int rng = R[q]-L[q];
		int s = L[q]+2;
		L[q] = clmb(L[q]+1);
		rng--;
		while(rng--){
			int p = clmb(s);
			upd(p, -1);
		}
		R[q] = clmb(s)-1;
		lft[L[q]].push_back(q);
		rht[R[q]].push_back(q);
		//cout << L[q] << " " << R[q] << endl;
	}
	fill(bit, bit+1+N, 0);
	for(int i = 1; i<N; i++){
		if(arr[i-1] > K){
			upd(i, 1);
		}
	}
	for(int q = 0; q<Q; q++){
		if(query(R[q]) == query(L[q]-1)){
			good[q] = 1;
		}
	}
	int ans = 0;
	for(int i = 1; i<=N; i++){
		for(int q : lft[i]){
			if(good[q]){
				upd(q+1, 1);
			}
			else{
				st.insert(q+1);
			}
		}
		if(st.empty()){
			ans = max(ans, query(Q));
		}
		else{
			ans = max(ans, query(*st.begin()));
		}
		for(int q : rht[i]){
			if(good[q]){
				upd(q+1, -1);
			}
			else{
				st.erase(q-1);
			}
		}
	}
	return ans;
}
/*
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int LL[3] = {1, 0, 0};
	int RR[3] = {3, 1, 1};
	int AA[4] = {1, 0, 2, 4};
	cout << GetBestPosition(5, 3, 3, AA, LL, RR) << endl;
}
*/

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