제출 #237702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
237702		kartel	Krov (COCI17_krov)	C++14	140 / 140	777 ms	8792 KiB

krov

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
#define N +100500
#define MaxS N * N
#define M ll(1e9 + 7)
#define sz(x) (int)x.size()
//#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;

vector <ll> Sum[2];
vector <ll> Kol[2], Vec[2], SVec[2];
ll s[2];
ll nn[2];
ll h[N], ans, i, n, mid, l, r;

void leftupdkol(ll v, ll value) {for (v++; v < sz(Kol[0]); v += v & -v) Kol[0][v] += value;}
void rightupdkol(ll v, ll value) {for (v++; v < sz(Kol[1]); v += v & -v) Kol[1][v] += value;}

void leftupdsum(ll v, ll value) {for (v++; v < sz(Sum[0]); v += v & -v) Sum[0][v] += value;}
void rightupdsum(ll v, ll value) {for (v++; v < sz(Sum[1]); v += v & -v) Sum[1][v] += value;}

ll getleftkol(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Kol[0][v];return res;}
ll getrightkol(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Kol[1][v];return res;}

ll getleftsum(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Sum[0][v];return res;}
ll getrightsum(ll v){ll res = 0; for (v++; v > 0; v -= v & -v) res += Sum[1][v];return res;}

ll getleftind(ll x) {return (upper_bound(SVec[0].begin(), SVec[0].end(), x) - SVec[0].begin()) - 1;}
ll getrightind(ll x) {return (upper_bound(SVec[1].begin(), SVec[1].end(), x) - SVec[1].begin()) - 1;}

void addleft(ll v)
{
    ll u = getleftind(Vec[0][v]);
    leftupdkol(u, 1);
    leftupdsum(u, Vec[0][v]);

    nn[0]++;
    s[0] += Vec[0][v];
}

void addright(ll v)
{
    ll u = getrightind(Vec[1][v]);
//    cerr << v << el;
    rightupdkol(u, 1);
    rightupdsum(u, Vec[1][v]);

    nn[1]++;
    s[1] += Vec[1][v];
}

void removeleft(ll v)
{
    ll u = getleftind(Vec[0][v]);
    leftupdkol(u, -1);
    leftupdsum(u, -Vec[0][v]);

    nn[0]--;
    s[0] -= Vec[0][v];
}

void removeright(ll v)
{
    ll u = getrightind(Vec[1][v]);
    rightupdkol(u, -1);
    rightupdsum(u, -Vec[1][v]);

    nn[1]--;
    s[1] -= Vec[1][v];
}

ll leftF(ll v)
{
    ll u = getleftind(v);
    if (u < 0) return s[0] - nn[0] * 1ll * v;

    ll le = getleftkol(u);
    ll ri = nn[0] - le;

    ll leftsum = getleftsum(u);
//    cerr << s[0] << " " << nn[0] << " " << le << " " << leftsum << el;
    ll rightsum = s[0] - leftsum;

    return le * v - leftsum + rightsum - ri * v;
}

ll rightF(ll v)
{
    ll u = getrightind(v);
    if (u < 0) return s[1] - nn[1] * 1ll * v;

    ll le = getrightkol(u);
    ll ri = nn[1] - le;

    ll leftsum = getrightsum(u);
//    cerr << s[1] << " " << nn[1] << " " << le << " " << leftsum << el;
    ll rightsum = s[1] - leftsum;

    return le * v - leftsum + rightsum - ri * v;
}

int main()
{
    srand(time(0));
    ios_base::sync_with_stdio(0);
    iostream::sync_with_stdio(0);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

//    in("input.txt");
//    out("output.txt");

    cin >> n;
    for (i = 0; i < n; i++) cin >> h[i];

    ans = 1e18;

    for (i = 0; i < n; i++) Vec[0].pb(h[i] - i), Vec[1].pb(h[i] + i);

    SVec[0] = Vec[0];
    SVec[1] = Vec[1];

    sort(SVec[0].begin(), SVec[0].end());
    sort(SVec[1].begin(), SVec[1].end());

    Sum[0].assign(n + 10, 0);
    Sum[1].assign(n + 10, 0);
    Kol[0].assign(n + 10, 0);
    Kol[1].assign(n + 10, 0);

    for (i = 0; i < n; i++) addright(i);

    for (mid = 0; mid < n; mid++)
    {
        addleft(mid);
        removeright(mid);
        l = max(mid + 1, n - mid);
        r = 2e9;

        while (r - l > 10)
        {
            ll m1 = (l + r) / 2ll, m2 = m1 + 1;
            ll f1 = leftF(m1 - mid) + rightF(m1 + mid);
            ll f2 = leftF(m2 - mid) + rightF(m2 + mid);

            if (f1 <= f2) r = m1;
            else l = m2;
        }

        for (; l <= r; l++)
        {
//            cerr << mid << " " << l << " " << leftF(l - mid) + rightF(l + mid) << el;
            ans = min(ans, leftF(l - mid) + rightF(l + mid));
        }
    }

    cout << ans;
}

//  x ^ 2 + y ^ 2 = 1
//  x * a_i + y * b_i
//  a_i = -b_i * tan(alpha)
//  a_i / -b_i = tan(alpha)
//  alpha = atan(a_i / (-b_i))

• 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