Submission #98111

#	Time	Username	Problem	Language	Result	Execution time	Memory
98111		dalgerok	Krov (COCI17_krov)	C++17	140 / 140	466 ms	7152 KiB

krov

#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5;



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

vector < int > E;
inline int Find(int x){
    return lower_bound(E.begin(), E.end(), x) - E.begin() + 1;
}

struct fenwick{
    int t[2 * N];
    long long f[2 * N];
    inline void Insert(int val){
        int pos = Find(val);
        for(int i = pos; i < 2 * N; i |= i + 1){
            t[i] += 1;
            f[i] += val;
        }
    }
    inline void Erase(int val){
        int pos = Find(val);
        for(int i = pos; i < 2 * N; i |= i + 1){
            t[i] -= 1;
            f[i] -= val;
        }
    }
    inline int Get_cnt(int val){
        int pos = Find(val + 1) - 1, res = 0;
        for(int i = pos; i >= 1; i &= i + 1, i--){
            res += t[i];
        }
        return res;
    }
    inline long long Get_sum(int val){
        int pos = Find(val + 1) - 1;
        long long res = 0;
        for(int i = pos; i >= 1; i &= i + 1, i--){
            res += f[i];
        }
        return res;
    }
    inline long long Get_ans(int val){
        int cnt_left = Get_cnt(val),
            cnt_right = Get_cnt(2e9) - cnt_left;
        long long sum_left = Get_sum(val),
                  sum_right = Get_sum(2e9) - sum_left;
        return (1LL * val * cnt_left - sum_left) + (sum_right - 1LL * val * cnt_right);
    }
}t_left, t_right;


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(t_left.Get_cnt(mid - i) + t_right.Get_cnt(mid + i) >= (n + 1) / 2){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    ans = min(ans, t_left.Get_ans(l - i) + t_right.Get_ans(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];
        E.push_back(a[i] + i);
        E.push_back(a[i] - i);
    }
    sort(E.begin(), E.end());
    E.resize(unique(E.begin(), E.end()) - E.begin());
    for(int i = 1; i <= n; i++){
        t_right.Insert(a[i] + i);
    }
    for(int i = 1; i <= n; i++){
        t_right.Erase(a[i] + i);
        t_left.Insert(a[i] - i);
        Get_median(i);
    }
    cout << ans;
}

Compilation message (stderr)

krov.cpp: In function 'int Get_median(int)':
krov.cpp:71: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: 14 / 14