oj.uz

Submission #24810

# Submission time Handle Problem Language Result Execution time Memory
24810 2017-06-14T08:28:50 Z Extazy medians (balkan11_medians) C++14
5 / 100
 300 ms 5092 KB 
#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-1,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+1,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

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.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5092 KB Integer 20 violates the range [1, 19]
2 Incorrect 0 ms 5092 KB Integer 40 violates the range [1, 39]
3 Execution timed out 300 ms 5092 KB Execution timed out
4 Execution timed out 300 ms 5092 KB Execution timed out
5 Incorrect 0 ms 5092 KB Integer 100 violates the range [1, 99]
6 Correct 0 ms 5092 KB Output is correct
7 Execution timed out 300 ms 5092 KB Execution timed out
8 Execution timed out 300 ms 5092 KB Execution timed out
9 Incorrect 0 ms 5092 KB Integer 180 violates the range [1, 179]
10 Execution timed out 300 ms 5092 KB Execution timed out
11 Incorrect 0 ms 5092 KB Integer 600 violates the range [1, 599]
12 Execution timed out 300 ms 5092 KB Execution timed out
13 Incorrect 0 ms 5092 KB Integer 2000 violates the range [1, 1999]

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5092 KB Integer 4000 violates the range [1, 3999]
2 Execution timed out 300 ms 5092 KB Execution timed out
3 Incorrect 6 ms 5092 KB Integer 16000 violates the range [1, 15999]
4 Incorrect 19 ms 5092 KB Integer 32000 violates the range [1, 31999]
5 Execution timed out 300 ms 5092 KB Execution timed out
6 Execution timed out 300 ms 5092 KB Execution timed out
7 Execution timed out 300 ms 5092 KB Execution timed out