oj.uz

Submission #737999

# Submission time Handle Problem Language Result Execution time Memory
737999 2023-05-08T04:42:49 Z GrindMachine Krov (COCI17_krov) C++17
98 / 140
 1500 ms 5944 KB 
// 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) >= ceil2(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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 456 KB Output is correct
2 Correct 12 ms 492 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 472 KB Output is correct
2 Correct 14 ms 468 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 596 KB Output is correct
2 Correct 39 ms 596 KB Output is correct
3 Correct 15 ms 596 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 866 ms 1712 KB Output is correct
2 Correct 926 ms 1864 KB Output is correct
3 Correct 903 ms 1756 KB Output is correct
4 Correct 1295 ms 2216 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 2632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 4400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 5944 KB Time limit exceeded
2 Halted 0 ms 0 KB -