oj.uz

Submission #98110

# Submission time Handle Problem Language Result Execution time Memory
98110 2019-02-20T18:16:00 Z dalgerok Krov (COCI17_krov) C++17
126 / 140
 1500 ms 6432 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;



int n, a[N];
long long ans = 9e18;

struct item{
    item *l, *r;
    int key, prior, cnt;
    long long sum;
    item(){}
    item(int x){
        key = sum = x;
        cnt = 1;
        prior = (rand() ^ (rand() << 15));
        l = r = nullptr;
    }
};
typedef item *pitem;
pitem t_left = nullptr, t_right = nullptr;

inline long long sum(pitem v){
    return v ? v->sum : 0;
}
inline int cnt(pitem v){
    return v ? v->cnt : 0;
}
inline void upd_cnt(pitem &v){
    if(v){
        v->cnt = cnt(v->l) + 1 + cnt(v->r);
        v->sum = sum(v->l) + v->key + sum(v->r);
    }
}
void Merge(pitem &v, pitem l, pitem r){
    if(!l || !r){
        v = l ? l : r;
        return;
    }
    if(l->prior > r->prior){
        Merge(l->r, l->r, r);
        v = l;
    }
    else{
        Merge(r->l, l, r->l);
        v = r;
    }
    upd_cnt(v);
}
void Split(pitem v, int key, pitem &l, pitem &r){
    if(!v){
        l = r = nullptr;
        return;
    }
    if(key < v->key){
        Split(v->l, key, l, v->l);
        r = v;
    }
    else{
        Split(v->r, key, v->r, r);
        l = v;
    }
    upd_cnt(v);
}

inline void Insert(pitem &v, int key){
    pitem t;
    Split(v, key, v, t);
    Merge(v, v, new item(key));
    Merge(v, v, t);
}

void Erase(pitem &v, int key){
    if(!v){
        assert(false);
    }
    if(v->key == key){
        pitem th = v;
        Merge(v, v->l, v->r);
        delete th;
    }
    else{
        Erase(key < v->key ? v->l : v->r, key);
    }
    upd_cnt(v);
}

inline int Get_cnt(pitem &v, int val){
    pitem tr;
    Split(v, val, v, tr);
    int res = cnt(v);
    Merge(v, v, tr);
    return res;
}
inline long long Get_sum(pitem &v, int val){
    pitem tr;
    Split(v, val, v, tr);
    long long res = (1LL * val * cnt(v) - sum(v)) + (sum(tr) - 1LL * val * cnt(tr));
    Merge(v, v, tr);
    return res;
}

inline int Get_median(int i){
    int l = max(i, n - i + 1), r = 1e9 + 1e6;
    while(r > l){
        int mid = (r + l) >> 1;
        if(Get_cnt(t_left, mid - i) + Get_cnt(t_right, mid + i) >= (n + 1) / 2){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    ans = min(ans, Get_sum(t_left, l - i) + Get_sum(t_right, l + i));
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    vector < int > q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        Insert(t_right, a[i] + i);
    }
    for(int i = 1; i <= n; i++){
        Erase(t_right, a[i] + i);
        Insert(t_left, a[i] - i);
        Get_median(i);
    }
    cout << ans;
}

Compilation message

krov.cpp: In function 'int Get_median(int)':
krov.cpp:119:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Correct 10 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 11 ms 384 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 14 ms 512 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 512 KB Output is correct
2 Correct 23 ms 524 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 556 KB Output is correct
2 Correct 18 ms 512 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 768 KB Output is correct
2 Correct 39 ms 640 KB Output is correct
3 Correct 24 ms 544 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 1812 KB Output is correct
2 Correct 333 ms 1900 KB Output is correct
3 Correct 290 ms 1912 KB Output is correct
4 Correct 381 ms 2296 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 2652 KB Output is correct
2 Correct 701 ms 3064 KB Output is correct
3 Correct 754 ms 2680 KB Output is correct
4 Correct 523 ms 2680 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1286 ms 4692 KB Output is correct
2 Correct 1386 ms 5020 KB Output is correct
3 Correct 447 ms 2552 KB Output is correct
4 Correct 991 ms 4728 KB Output is correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1550 ms 6432 KB Time limit exceeded
2 Halted 0 ms 0 KB -