oj.uz

Submission #155862

# Submission time Handle Problem Language Result Execution time Memory
155862 2019-10-01T06:46:30 Z oolimry Jousting tournament (IOI12_tournament) C++14
100 / 100
 265 ms 7884 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 632 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 9 ms 760 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 9 ms 632 KB Output is correct
7 Correct 9 ms 684 KB Output is correct
8 Correct 9 ms 632 KB Output is correct
9 Correct 4 ms 760 KB Output is correct
10 Correct 14 ms 764 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4080 KB Output is correct
2 Correct 217 ms 7652 KB Output is correct
3 Correct 77 ms 6960 KB Output is correct
4 Correct 213 ms 7884 KB Output is correct
5 Correct 207 ms 7412 KB Output is correct
6 Correct 265 ms 7544 KB Output is correct
7 Correct 214 ms 7672 KB Output is correct
8 Correct 211 ms 7672 KB Output is correct
9 Correct 67 ms 7284 KB Output is correct
10 Correct 88 ms 7664 KB Output is correct