Submission #237702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
237702	2020-06-08T11:29:25 Z	kartel	Krov (COCI17_krov)	C++14	140 / 140	777 ms	8792 KB

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

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	640 KB	Output is correct
2	Correct	20 ms	512 KB	Output is correct

Subtask #6
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	888 KB	Output is correct
2	Correct	31 ms	768 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	180 ms	2300 KB	Output is correct
2	Correct	178 ms	2428 KB	Output is correct
3	Correct	174 ms	2396 KB	Output is correct
4	Correct	218 ms	2812 KB	Output is correct

Subtask #8
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	298 ms	3572 KB	Output is correct
2	Correct	317 ms	3956 KB	Output is correct
3	Correct	243 ms	3700 KB	Output is correct
4	Correct	232 ms	3816 KB	Output is correct

Subtask #9
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	562 ms	6368 KB	Output is correct
2	Correct	450 ms	6508 KB	Output is correct
3	Correct	267 ms	3316 KB	Output is correct
4	Correct	574 ms	6500 KB	Output is correct

Subtask #10
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	667 ms	8792 KB	Output is correct
2	Correct	693 ms	8640 KB	Output is correct
3	Correct	559 ms	6372 KB	Output is correct
4	Correct	777 ms	8036 KB	Output is correct
5	Correct	156 ms	2428 KB	Output is correct

Submission #237702

Compilation message