Submission #737997

#	Time	Username	Problem	Language	Result	Execution time	Memory
737997		GrindMachine	Krov (COCI17_krov)	C++17	56 / 140	1572 ms	5952 KiB

krov

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/56372?#comment-400794

made the first few observations, but didnt know how to optimize

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        i++;

        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        i++;

        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n + 5);
    rep1(i, n) cin >> a[i];

    vector<ll> b1, b2;
    rep1(i, n) {
        b1.pb(a[i] - i);
        b2.pb(a[i] + i);
    }

    sort(all(b1)), sort(all(b2));
    b1.resize(unique(all(b1)) - b1.begin());
    b2.resize(unique(all(b2)) - b2.begin());

    fenwick<ll> fenw_cnt_1(n + 5), fenw_cnt_2(n + 5);
    fenwick<ll> fenw_sum_1(n + 5), fenw_sum_2(n + 5);

    rep1(i, n) {
        ll ind = lower_bound(all(b2), a[i] + i) - b2.begin();
        fenw_cnt_2.pupd(ind, 1);
        fenw_sum_2.pupd(ind, a[i] + i);
    }

    auto get_cnt = [&](ll i, ll m) {
        ll cnt = 0;

        ll ind1 = upper_bound(all(b1), m - i) - b1.begin() - 1;
        cnt += fenw_cnt_1.query(0, ind1);

        ll ind2 = upper_bound(all(b2), m + i) - b2.begin() - 1;
        cnt += fenw_cnt_2.query(0, ind2);

        return cnt;
    };

    auto get_ops = [&](ll i, ll m) {
        ll sum = 0;

        ll ind = lower_bound(all(b1), m - i) - b1.begin();
        ll cnt1 = fenw_cnt_1.query(ind, n);
        ll sum1 = fenw_sum_1.query(ind, n);
        ll cnt2 = fenw_cnt_1.query(0, ind - 1);
        ll sum2 = fenw_sum_1.query(0, ind - 1);

        sum += sum1 - cnt1 * (m - i);
        sum += -sum2 + cnt2 * (m - i);

        ind = lower_bound(all(b2), m + i) - b2.begin();
        cnt1 = fenw_cnt_2.query(ind, n);
        sum1 = fenw_sum_2.query(ind, n);
        cnt2 = fenw_cnt_2.query(0, ind - 1);
        sum2 = fenw_sum_2.query(0, ind - 1);

        sum += sum1 - cnt1 * (m + i);
        sum += -sum2 + cnt2 * (m + i);

        return sum;
    };

    ll ans = inf2;

    rep1(i, n) {
        ll ind1 = lower_bound(all(b1), a[i] - i) - b1.begin();
        ll ind2 = lower_bound(all(b2), a[i] + i) - b2.begin();

        fenw_cnt_1.pupd(ind1, 1);
        fenw_cnt_2.pupd(ind2, -1);

        fenw_sum_1.pupd(ind1, a[i] - i);
        fenw_sum_2.pupd(ind2, -(a[i] + i));

        ll mxd = max((ll) i - 1, n - i);
        ll l = mxd + 1, r = 2 * inf1;
        ll best = -1;

        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (get_cnt(i, mid) >= n / 2) {
                best = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }

        ll ops = 0;

        rep1(j, n) {
            ll h = best - abs(i - j);
            ops += abs(a[j] - h);
        }

        amin(ans, ops);

        // ll ops = get_ops(i, best);
        // amin(ans, ops);
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

krov.cpp: In function 'void solve(int)':
krov.cpp:156:10: warning: variable 'get_ops' set but not used [-Wunused-but-set-variable]
  156 |     auto get_ops = [&](ll i, ll m) {
      |          ^~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14