Submission #24809

#	Time	Username	Problem	Language	Result	Execution time	Memory
24809		Extazy	medians (balkan11_medians)	C++14	5 / 100	300 ms	5092 KiB

medians

#include <bits/stdc++.h>
#define next afgqfqqfqfq
#define prev klajhgjahgjka

using namespace std;

const int N = 1<<18;

int n,a[N],b[N],it[N];

void update(int pos, int val) {
    for(;pos<2*n;pos+=pos&(-pos)) it[pos]+=val;
}

int query(int pos) {
    int ans=0;
    for(;pos>=1;pos-=pos&(-pos)) ans+=it[pos];
    return ans;
}

int query(int l, int r) {
    return query(r)-query(l-1);
}

int next(int pos) {
    int left=pos,right=2*n,middle;
    while(right-left>1) {
        middle=(left+right)>>1;
        if(query(pos,middle)==middle-pos+1) left=middle;
        else right=middle;
    }
    return right;
}

int prev(int pos) {
    int left=0,right=pos,middle;
    while(right-left>1) {
        middle=(left+right)>>1;
        if(query(middle,pos)==pos-middle+1) right=middle;
        else left=middle;
    }
    return left;
}

int main() {
    int i;
    
    scanf("%d", &n);
    for(i=1;i<=n;i++) {
        scanf("%d", &b[i]);
    }
    
    //Handle the first element
    a[1]=b[1];
    update(a[1],1);
    
    //Handle the second and third element
    if(b[1]!=b[2]) {
        a[2]=b[2];
        update(a[2],1);
        if(a[2]<a[1]) {
            a[3]=a[2]-1;
        }
        else {
            a[3]=a[2]+1;
        }
        update(a[3],1);
    }
    else {
        a[2]=a[1]-1;
        a[3]=a[1]+1;
        update(a[2],1);
        update(a[3],1);
    }
    
    for(i=3;i<=n;i++) {
        if(b[i]==b[i-1]) {
            a[2*(i-1)]=prev(b[i]);
            update(a[2*(i-1)],1);
            a[2*(i-1)+1]=next(b[i]);
            update(a[2*(i-1)+1],1);
        }
        else if(b[i]>b[i-1]) {
            a[2*(i-1)]=next(b[i]);
            update(a[2*(i-1)],1);
            a[2*(i-1)+1]=next(b[i]);
            update(a[2*(i-1)+1],1);
        }
        else {
            a[2*(i-1)]=prev(b[i]);
            update(a[2*(i-1)],1);
            a[2*(i-1)+1]=prev(b[i]);
            update(a[2*(i-1)+1],1);
        }
    }
    for(i=1;i<2*n;i++) {
        if(i>1) printf(" ");
        printf("%d", a[i]);
    }
    printf("\n");
    
    return 0;
}

Compilation message (stderr)

medians.cpp: In function 'int main()':
medians.cpp:48:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
medians.cpp:50:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &b[i]);
                           ^

• Subtask 1: 5 / 65
• Subtask 2: 0 / 35