Submission #155862

#	Time	Username	Problem	Language	Result	Execution time	Memory
155862		oolimry	Jousting tournament (IOI12_tournament)	C++14	100 / 100	265 ms	7884 KiB

tournament

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

int tree[200005];

int n;
void update(int i, int x){
	i += n;
	while(i > 0){
		tree[i] += x;
		i >>= 1;
	}
}

int query(int l, int r){
	int ans = 0;
	for(l += n,r += n;l < r;l >>= 1, r >>= 1){
		if(l&1){
			ans += tree[l];
			l++;
		}
		if(r&1){
			r--;
			ans += tree[r];
		}
	}
	return ans;
}

int tree2[200005];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N;
	typedef pair<int,int> ii;
	vector<ii> actual;
	set<int> stuff;
	for(int i = 0;i < n;i++){
		stuff.insert(i);
		update(i,1);
	}
	vector<int> big;
	for(int i = 0;i < n-1;i++){
		if(K[i] > R) big.push_back(i);
	}
	//cout << query(1,2) << "\n";
	for(int i = 0;i < C;i++){
		int s = S[i];
		int e = E[i];
		int l, r;
		
		if(s == 0){
			l = 0;
		}
		else{
			int low = 0;
			int high = n;
			while(true){
				if(low == high - 1) break;
				int ss = (low + high) / 2;
				if(query(0, ss + 1) <= s){
					low = ss;
				} 
				else{
					high = ss;
				}
			}
			l = high;
		}
		
		if(false){
			r = n;
		}
		else{
			int low = 0;
			int high = n;
			while(true){
				if(low == high - 1) break;
				int ss = (low + high) / 2;
				if(query(0, ss + 1) <= e + 1){
					low = ss;
				} 
				else{
					high = ss;
				}
			}
			r = high;
		}
		
		//if(i == 1) break;
		
		if(i != C-1){
			
			set<int>::iterator it = stuff.find(l);
			vector<int> removed;
			while(true){
				it++;
				if(it == stuff.end()) break;
				if(*it == r) break;
				removed.push_back(*it);
			}
			for(int j = 0;j < removed.size();j++){
				stuff.erase(removed[j]);
				update(removed[j],-1);
			}
		}
		
		r--;
		//cout << l << " " << r << "\n";
		if(lower_bound(big.begin(),big.end(),l) == upper_bound(big.begin(),big.end(),r-1)){
			//cout << l << " " << r << " " << "good\n";
			for(l += n, r += (n+1);l < r;l >>= 1, r >>= 1){
				if(l&1){
					tree2[l]++;
					l++;
				}
				if(r&1){
					r--;
					tree2[r]++;
				}
			}
		}
	}
	ii best = ii(0,-102345678);
	for(int i = 0;i < n;i++){
		int x = i + n;
		
		int ans = 0;
		while(x > 0){
			ans += tree2[x];
			x >>= 1;
		}
		
		best = max(best, ii(ans,-1*i));
		//cout << ans << "\n";
	}
	
	return best.second * -1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:101:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0;j < removed.size();j++){
                  ~~^~~~~~~~~~~~~~~~

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