oj.uz

Submission #236795

# Submission time Handle Problem Language Result Execution time Memory
236795 2020-06-03T10:22:44 Z VEGAnn Krov (COCI17_krov) C++14
140 / 140
 764 ms 5228 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct
2 Correct 14 ms 384 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 640 KB Output is correct
2 Correct 27 ms 512 KB Output is correct
3 Correct 17 ms 512 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 1536 KB Output is correct
2 Correct 164 ms 1280 KB Output is correct
3 Correct 182 ms 1536 KB Output is correct
4 Correct 237 ms 1792 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 2164 KB Output is correct
2 Correct 358 ms 2548 KB Output is correct
3 Correct 226 ms 2420 KB Output is correct
4 Correct 227 ms 2292 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 2796 KB Output is correct
2 Correct 437 ms 3944 KB Output is correct
3 Correct 266 ms 2200 KB Output is correct
4 Correct 576 ms 3816 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 5228 KB Output is correct
2 Correct 658 ms 5228 KB Output is correct
3 Correct 587 ms 3816 KB Output is correct
4 Correct 764 ms 4844 KB Output is correct
5 Correct 157 ms 1660 KB Output is correct