이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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++){
if(query(R[q]-1) == query(L[q]-1)){
good[q] = 1;
}
}
int ans = 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()){
ans = max(ans, query(Q));
}
else{
ans = max(ans, query(*st.begin()));
}
for(int q : rht[i]){
if(good[q]){
upd(q+1, -1);
}
else{
st.erase(q-1);
}
}
}
return ans;
}
/*
int main(){
cin.sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int LL[3] = {1, 0, 0};
int RR[3] = {3, 1, 1};
int AA[4] = {1, 0, 2, 4};
cout << GetBestPosition(5, 3, 3, AA, LL, RR) << endl;
}
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |