Submission #480732

#	Time	Username	Problem	Language	Result	Execution time	Memory
480732		phamhoanghiep	medians (balkan11_medians)	C++14	100 / 100	64 ms	2812 KiB

medians

#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 / 65
• Subtask 2: 35 / 35