Submission #98110

#	Time	Username	Problem	Language	Result	Execution time	Memory
98110		dalgerok	Krov (COCI17_krov)	C++17	126 / 140	1550 ms	6432 KiB

krov

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 0 / 14