oj.uz

답안 #155857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
155857 2019-10-01T06:21:08 Z oolimry 마상시합 토너먼트 (IOI12_tournament) C++14
0 / 100
 80 ms 3696 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;
		
		
		
		
	}
	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

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

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

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 3696 KB Output isn't correct
2 Halted 0 ms 0 KB -