Submission #1267561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267561		canhnam357	Krov (COCI17_krov)	C++20	140 / 140	609 ms	9196 KiB

krov

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
struct fenwick {
    int n;
    vector<int> bit;
    fenwick() {}
    fenwick(int n) {
        this->n = n + 5;
        bit.resize(n + 5);
    }
    void add(int pos, int val) {
        while (pos < n) {
            bit[pos] += val;
            pos += pos & -pos;
        }
    }
    int get(int pos) {
        if (pos < 0) return 0;
        int ans = 0;
        while (pos) {
            ans += bit[pos];
            pos -= pos & -pos;
        }
        return ans;
    }
    int get(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
};
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), cc;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cc.push_back(a[i] + i);
        cc.push_back(a[i] - i);
    }
    sort(all(cc));
    cc.erase(unique(all(cc)), cc.end());
    int m = cc.size();
    auto get_pos = [&](int pos) {
        if (pos > cc.back()) return m + 1;
        return (int)(upper_bound(all(cc), pos) - cc.begin());
    };
    int ans = LLONG_MAX;
    /*
        left  : a[j] - (a[i] - (i - j)) = (a[j] - j) - (a[i] - i)
        right : a[j] - (a[i] - (j - i)) = (a[j] + j) - (a[i] + i)
    */
    /*
        Cố định cột i là đỉnh, tìm kiếm tam phân để tìm ra chiều cao tối thiểu chi phí thay đổi
    */
    fenwick occ_left(m), sum_left(m), occ_right(m), sum_right(m);
    for (int i = 0; i < n; i++) {
        int pos = get_pos(a[i] + i);
        occ_right.add(pos, 1);
        sum_right.add(pos, a[i] + i);
    }
    auto f = [&](int h, int i) {
        int cost = 0;
        {
            int p = get_pos(h - i);
            int k = h - i;
            cost += occ_left.get(p) * k - sum_left.get(p);
            cost += sum_left.get(p + 1, m)  - k * occ_left.get(p + 1, m);
        }
        {
            int p = get_pos(h + i);
            int k = h + i;
            cost += occ_right.get(p) * k    - sum_right.get(p);
            cost += sum_right.get(p + 1, m) - k * occ_right.get(p + 1, m);
        }
        return cost;
    };
    auto g = [&](int h, int i) {
        int cost = 0;
        for (int j = 0; j < i; j++) {
            cost += abs(a[j] - j - (h - i));
        }
        for (int j = i; j < n; j++) {
            cost += abs(a[j] + j - (h + i));
        }
        return cost;
    };
    for (int i = 0; i < n; i++) {
        int left_bound = max(i + 1, n - i);
        int right_bound = 1e9;
        // cout << "POS " << i << '\n';
        // for (int j = left_bound; j <= 10; j++) {
        //     cout << j << ' ' << f(j, i) << ' ' << g(j, i) << '\n';
        // }
        int l = left_bound, r = right_bound;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (f(mid, i) <= f(mid - 1, i)) l = mid;
            else r = mid;
        }
        ans = min({ans, f(left_bound, i), f(right_bound, i), f(l, i)});
        int pos = get_pos(a[i] - i);
        occ_left.add(pos, 1);
        sum_left.add(pos, a[i] - i);
        pos = get_pos(a[i] + i);
        occ_right.add(pos, -1);
        sum_right.add(pos, -a[i] - i);
    }
    cout << ans << '\n';
    return 0;
}

• 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