Submission #155857

#	Time	Username	Problem	Language	Result	Execution time	Memory
155857		oolimry	Jousting tournament (IOI12_tournament)	C++14	0 / 100	80 ms	3696 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(query(0,n) == e + 1){
			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;
		
		
		
		
	}
	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 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:49:7: warning: variable 'l' set but not used [-Wunused-but-set-variable]
   int l, r;
       ^
tournament.cpp:49:10: warning: variable 'r' set but not used [-Wunused-but-set-variable]
   int l, r;
          ^

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