oj.uz

Submission #98111

# Submission time Handle Problem Language Result Execution time Memory
98111 2019-02-20T18:26:02 Z dalgerok Krov (COCI17_krov) C++17
140 / 140
 466 ms 7152 KB 
#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

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

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 768 KB Output is correct
2 Correct 14 ms 640 KB Output is correct
3 Correct 12 ms 640 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1792 KB Output is correct
2 Correct 102 ms 1408 KB Output is correct
3 Correct 92 ms 1792 KB Output is correct
4 Correct 115 ms 2176 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2420 KB Output is correct
2 Correct 181 ms 2740 KB Output is correct
3 Correct 125 ms 2940 KB Output is correct
4 Correct 131 ms 2776 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 2436 KB Output is correct
2 Correct 220 ms 4704 KB Output is correct
3 Correct 136 ms 2292 KB Output is correct
4 Correct 279 ms 4076 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 364 ms 6484 KB Output is correct
2 Correct 318 ms 7152 KB Output is correct
3 Correct 298 ms 4724 KB Output is correct
4 Correct 466 ms 5768 KB Output is correct
5 Correct 73 ms 2296 KB Output is correct