oj.uz

답안 #480732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480732 2021-10-18T01:49:43 Z phamhoanghiep 중앙값 배열 (balkan11_medians) C++14
100 / 100
 64 ms 2812 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
bool ck[maxn];
int a[maxn];
int n;
int bit[maxn];
void upd(int pos, int val) {
    for(int i=pos ; i<=2*n-1 ; i+=i&-i) {
        bit[i]+=val;
    }
}
int pf(int pos) {
    int res=0;
    for(int i=pos ; i>=1 ; i-=i&-i) {
        res+=bit[i];
    }
    return res;
}
int sum(int l, int r) {
    return pf(r)-pf(l-1);
}
signed main() {
    cin>>n;
    for(int i=1 ; i<=n ; i++) {
        cin>>a[i];
    }
    int l=1;
    int r=2*n-1;
    for(int i=1 ; i<=n ; i++) {
        int sm=sum(1,a[i]-1);
        int lg=sum(a[i]+1,2*n-1);
        if(!ck[a[i]]) {
            cout<<a[i]<<' ';
            ck[a[i]]=1;
            upd(a[i],1);
        }
        while(sm<lg) {
            while(ck[l]) l++;
            cout<<l<<' ';
            ck[l]=1;
            upd(l,1);
            sm++;
        }
        while(lg<sm) {
            while(ck[r]) r--;
            cout<<r<<' ';
            ck[r]=1;
            upd(r,1);
            lg++;
        }
        if(sm+lg<2*(i-1)) {
            while(ck[l]) l++;
            cout<<l<<' ';
            ck[l]=1;
            upd(l,1);
            while(ck[r]) r--;
            cout<<r<<' ';
            ck[r]=1;
            upd(r,1);
        }
    }
}

Subtask #1
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 5 ms 484 KB Output is correct
4 Correct 10 ms 632 KB Output is correct
5 Correct 21 ms 1076 KB Output is correct
6 Correct 38 ms 1912 KB Output is correct
7 Correct 64 ms 2812 KB Output is correct