oj.uz

답안 #155858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155858 2019-10-01T06:21:57 Z oolimry 마상시합 토너먼트 (IOI12_tournament) C++14
0 / 100
 277 ms 9432 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(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;
		
		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:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0;j < removed.size();j++){
                  ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Incorrect 2 ms 376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 9 ms 760 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 10 ms 760 KB Output is correct
5 Correct 9 ms 760 KB Output is correct
6 Correct 9 ms 760 KB Output is correct
7 Correct 9 ms 760 KB Output is correct
8 Correct 9 ms 764 KB Output is correct
9 Incorrect 4 ms 760 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 4092 KB Output is correct
2 Correct 219 ms 9276 KB Output is correct
3 Correct 79 ms 7544 KB Output is correct
4 Correct 216 ms 9432 KB Output is correct
5 Correct 211 ms 9008 KB Output is correct
6 Correct 277 ms 8796 KB Output is correct
7 Correct 217 ms 9340 KB Output is correct
8 Correct 225 ms 9336 KB Output is correct
9 Incorrect 66 ms 7924 KB Output isn't correct
10 Halted 0 ms 0 KB -