Submission #236795

#	Time	Username	Problem	Language	Result	Execution time	Memory
236795		VEGAnn	Krov (COCI17_krov)	C++14	140 / 140	764 ms	5228 KiB

krov

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
#define l2 array<ll,2>
using namespace std;
typedef long long ll;
const int N = 100100;
const int oo = int(2e9);
const ll OO = 1e18;
const int md = int(1e9) + 7;
vector<int> v[2];
int n;
ll x[N], ans = OO, pref_sum, suf_sum;
l2 fen[2][N];

void update(int tp, ll ps, int vl){
    ll mem = ps * vl;

    ps = lower_bound(all(v[tp]), ps) - v[tp].begin();

    for (; ps < sz(v[tp]); ps = (ps | (ps + 1))) {
        fen[tp][ps][0] += mem;
        fen[tp][ps][1] += vl;
    }
}

l2 get_fen(int tp, ll ps){
    l2 res = {0, 0};

    ps = upper_bound(all(v[tp]), ps) - v[tp].begin() - 1;

    for (; ps >= 0; ps = (ps & (ps + 1)) - 1){
        res[0] += fen[tp][ps][0];
        res[1] += fen[tp][ps][1];
    }

    return res;
}

ll get(int id, ll ht){
    ll cur = abs(x[id] - ht);

    if (id > 0) {
        l2 cr = get_fen(0, ht + (n - 1 - id));

        ll ost = pref_sum - cr[0];

        cur -= cr[0] - ((ll(n) - 1ll - ll(id)) * cr[1]);
        cur += ht * cr[1];

        cr[1] = id - cr[1];

        cur += ost - ((ll(n) - 1ll - ll(id)) * cr[1]);
        cur -= ht * cr[1];
    }

    if (id < n - 1){
        l2 cr = get_fen(1, ht + id);

//        cerr << cr[0] << " " << cr[1] << '\n';

        ll ost = suf_sum - cr[0];

        cur -= cr[0] - (ll(id) * cr[1]);
        cur += ht * cr[1];

        cr[1] = (n - 1 - id) - cr[1];

        cur += ost - (ll(id) * cr[1]);
        cur -= ht * cr[1];
    }

    return cur;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x[i];

        v[0].PB(x[i] + (n - 1 - i));
        v[1].PB(x[i] + i);
    }

    sort(all(v[0]));
    sort(all(v[1]));

    v[0].resize(unique(all(v[0])) - v[0].begin());
    v[1].resize(unique(all(v[1])) - v[1].begin());

    for (int i = 0; i < n; i++) {
        update(1, x[i] + i, 1);
        suf_sum += x[i] + i;
    }

    for (int i = 0; i < n; i++){
        update(1, x[i] + i, -1);
        suf_sum -= x[i] + i;

        ll l = max(i + 1, n - i), r = ll(1e9);

        while (l + 5 < r){
            ll md = (l + r) >> 1;

            if (get(i, md) < get(i, md + 1))
                r = md;
            else l = md + 1;
        }

        for (ll j = l; j <= r; j++)
            ans = min(ans, get(i, j));

        update(0, x[i] + (n - 1 - i), 1);
        pref_sum += x[i] + (n - 1 - i);
    }

    cout << ans;

    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