Submission #237702

#TimeUsernameProblemLanguageResultExecution timeMemory
237702kartelKrov (COCI17_krov)C++14
140 / 140
777 ms8792 KiB
#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))
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...