oj.uz

Submission #217107

# Submission time Handle Problem Language Result Execution time Memory
217107 2020-03-29T01:39:50 Z AQT Jousting tournament (IOI12_tournament) C++14
100 / 100
 108 ms 14328 KB 
//#include <tournament.h>
#include <bits/stdc++.h>

using namespace std;

int N;
int bit[100005];
bool good[100005];
vector<int> lft[100005];
vector<int> rht[100005];
set<int> st;

void upd(int p, int v){
	for(int i = p; i<=N; i+=i&-i){
		bit[i] += v;
	}
}

int query(int p){
	int ret = 0;
	while(p){
		ret += bit[p];
		p -= p&-p;
	}
	return ret;
}

int clmb(int lim){
	int tot = 0;
	int p = 0;
	for(int b = 16; b>=0; b--){
		if((1<<b)+p <= N && tot + bit[(1<<b)+p] < lim){
			tot += bit[(1<<b)+p];
			p += (1<<b);
		}
	}
	return p+1;
}

int GetBestPosition(int NN, int Q, int K, int arr[], int L[], int R[]){
	N = NN;
	for(int i = 1; i<=N; i++){
		upd(i, 1);
	}
	for(int q = 0; q<Q; q++){
		int rng = R[q]-L[q];
		int s = L[q]+2;
		L[q] = clmb(L[q]+1);
		while(rng--){
			int p = clmb(s);
			upd(p, -1);
		}
		R[q] = clmb(s)-1;
		lft[L[q]].push_back(q);
		rht[R[q]].push_back(q);
		//cout << L[q] << " " << R[q] << endl;
	}
	fill(bit, bit+1+N, 0);
	for(int i = 1; i<N; i++){
		if(arr[i-1] > K){
			upd(i, 1);
		}
	}
	for(int q = 0; q<Q; q++){
		good[q] = (query(R[q]-1) == query(L[q]-1));
	}
	fill(bit, bit+1+N, 0);
	int ans = -1, idx = 0;
	for(int i = 1; i<=N; i++){
		for(int q : lft[i]){
			if(good[q]){
				upd(q+1, 1);
			}
			else{
				st.insert(q+1);
			}
		}
		if(st.empty()){
			if(ans < query(Q)){
				ans = query(Q);
				idx = i-1;
			}
		}
		else{
			if(ans < query(*st.begin())){
				ans = query(*st.begin());
				idx = i-1;
			}
		}
		for(int q : rht[i]){
			if(good[q]){
				upd(q+1, -1);
			}
			else{
				st.erase(q+1);
			}
		}
	}
	return idx;
}
/*
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, Q, K;
	cin >> N >> Q >> K;
	int LL[Q], RR[Q], AA[N-1];
	for(int i = 0; i<N-1; i++){
		cin >> AA[i];
	}
	for(int i = 0; i<N; i++){
		cin >> LL[i] >> RR[i];
	}
	cout << GetBestPosition(N, Q, K, AA, LL, RR) << endl;
}
*/

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 8 ms 5120 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5120 KB Output is correct
8 Correct 7 ms 4992 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 11 ms 5504 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 11 ms 5376 KB Output is correct
5 Correct 11 ms 5376 KB Output is correct
6 Correct 11 ms 5248 KB Output is correct
7 Correct 11 ms 5376 KB Output is correct
8 Correct 11 ms 5376 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 12 ms 5376 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7032 KB Output is correct
2 Correct 108 ms 14328 KB Output is correct
3 Correct 39 ms 6784 KB Output is correct
4 Correct 98 ms 12528 KB Output is correct
5 Correct 95 ms 13048 KB Output is correct
6 Correct 86 ms 10232 KB Output is correct
7 Correct 98 ms 12792 KB Output is correct
8 Correct 107 ms 13400 KB Output is correct
9 Correct 36 ms 6400 KB Output is correct
10 Correct 40 ms 6776 KB Output is correct