Submission #1085227

#TimeUsernameProblemLanguageResultExecution timeMemory
1085227vladiliusMeetings (IOI18_meetings)C++17
60 / 100
5529 ms503004 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; using ll = long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second #define ins insert #define arr3 array<int, 3> const ll inf = 1e18; const int N = 7.5e5; struct DS{ struct line{ int k; ll b; ll operator ()(int x){ return 1LL * k * x + b; } line(int ks, ll bs){ k = ks; b = bs; } }; pair<int, ll> t[4 * N]; pll p[4 * N]; int n; DS(int ns){ n = ns; for (int i = 0; i < 4 * n; i++){ t[i] = {0, inf}; p[i] = {0, 0}; } } void apply(int v, pll x){ t[v].ff += x.ff; t[v].ss += x.ss; p[v].ff += x.ff; p[v].ss += x.ss; } void push1(int& v, int& tl, int& tr){ int vv = 2 * v; apply(vv, p[v]); apply(vv + 1, p[v]); p[v] = {0, 0}; } void push2(int& v, int& tl, int& tr){ int vv = 2 * v, tm = (tl + tr) / 2; insert(vv, tl, tm, t[v]); insert(vv + 1, tm + 1, tr, t[v]); t[v] = {0, inf}; } void insert(int v, int tl, int tr, pil f){ if (tl == tr){ if ((1LL * t[v].ff * tl + t[v].ss) > (1LL * f.ff * tl + f.ss)) t[v] = f; return; } int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); if (t[v].ff > f.ff) swap(t[v], f); if ((1LL * f.ff * tm + f.ss) <= (1LL * t[v].ff * tm + t[v].ss)){ swap(t[v], f); insert(vv + 1, tm + 1, tr, f); } else { insert(vv, tl, tm, f); } } void chmin(int v, int tl, int tr, int& l, int& r, pil& f){ if (l > tr || r < tl) return; if (l <= tl && tr <= r){ insert(v, tl, tr, f); return; } int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); chmin(vv, tl, tm, l, r, f); chmin(vv + 1, tm + 1, tr, l, r, f); } void chmin(int l, int r, int k, ll b){ pil f = {k, b}; chmin(1, 1, n, l, r, f); } void add(int v, int tl, int tr, int& l, int& r, pil& f){ if (l > tr || r < tl) return; if (l <= tl && tr <= r){ apply(v, {f.ff, f.ss}); return; } int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); push2(v, tl, tr); add(vv, tl, tm, l, r, f); add(vv + 1, tm + 1, tr, l, r, f); } void add(int l, int r, int k, ll b){ pil f = {k, b}; add(1, 1, n, l, r, f); } ll get(int v, int tl, int tr, int& x){ if (tl == tr) return (1LL * t[v].ff * x + t[v].ss); int tm = (tl + tr) / 2, vv = 2 * v; push1(v, tl, tr); if (x <= tm){ return min((1LL * t[v].ff * x + t[v].ss), get(vv, tl, tm, x)); } return min((1LL * t[v].ff * x + t[v].ss), get(vv + 1, tm + 1, tr, x)); } ll get(int x){ return get(1, 1, n, x); } }; vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){ const int A = 1e9; int n = (int) H.size(), q = (int) L.size(); vector<int> h(n + 1), aa; for (int i = 1; i <= n; i++){ h[i] = H[i - 1]; aa.pb(h[i]); } sort(aa.begin(), aa.end()); vector<int> vv; int i = 0; while (i < n){ int j = i; while (j < n && aa[i] == aa[j]){ j++; } vv.pb(aa[i]); i = j; } vector<int> :: iterator it; auto pos = [&](int x){ it = lower_bound(vv.begin(), vv.end(), x); int j = (int) (it - vv.begin()); return j; }; vector<int> d[(int) vv.size()]; for (int i = 1; i <= n; i++){ d[pos(h[i])].pb(i); } vector<int> log(n + 1); for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1; const int lg = log[n]; vector<vector<int>> pw(n + 1, vector<int>(lg + 1)), pw1(n + 1, vector<int>(lg + 1, A)); for (int i = 1; i <= n; i++) pw[i][0] = pw1[i][0] = h[i]; for (int j = 1; j <= lg; j++){ for (int i = 1; i + (1 << j) <= n + 1; i++){ pw[i][j] = max(pw[i][j - 1], pw[i + (1 << (j - 1))][j - 1]); pw1[i][j] = min(pw1[i][j - 1], pw1[i + (1 << (j - 1))][j - 1]); } } auto get = [&](int l, int r){ int k = log[r - l + 1]; return max(pw[l][k], pw[r - (1 << k) + 1][k]); }; auto getm = [&](int l, int r){ int k = log[r - l + 1]; return min(pw1[l][k], pw1[r - (1 << k) + 1][k]); }; vector<int> f; auto pp = [&](int x, int l, int r){ f.clear(); int X = pos(x); it = lower_bound(d[X].begin(), d[X].end(), l); while (it != d[X].end() && (*it) <= r){ f.pb((*it)); it++; } }; vector<pii> all1; auto gp = [&](int x, int l, int r){ pp(x, l, r); all1.clear(); int pre = l; for (int i: f){ if (pre < i){ all1.pb({pre, i - 1}); } pre = i + 1; } if (pre <= r) all1.pb({pre, r}); }; vector<pii> mp[(int) vv.size()]; function<void(int, int)> build1 = [&](int l, int r){ int m = get(l, r); mp[pos(m)].pb({l, r}); gp(m, l, r); vector<pii> all = all1; for (auto [l1, r1]: all){ build1(l1, r1); } }; build1(1, n); vector<ll> out(q + 1); map<pii, vector<arr3>> qs; for (int i = 1; i <= q; i++){ int l, r; l = L[i - 1]; r = R[i - 1]; l++; r++; if (get(l, r) == getm(l, r)){ out[i] = 1LL * h[l] * (r - l + 1); continue; } int k = pos(get(l, r)), l1 = 0, r1 = (int) mp[k].size() - 1; while (l1 + 1 < r1){ int m = (l1 + r1) / 2; if (mp[k][m].ff <= l){ l1 = m; } else { r1 = m - 1; } } if (mp[k][r1].ff <= l) l1 = r1; qs[mp[k][l1]].pb({l, r, i}); } DS T1(n), T2(n); vector<int> :: iterator it1, it2; function<void(int, int)> build = [&](int l, int r){ int m = get(l, r); gp(m, l, r); vector<pii> all = all1; for (auto [l1, r1]: all) build(l1, r1); if (all.empty()){ T1.add(l, r, m, -1LL * m * (l - 1)); T2.add(l, r, -m, 1LL * m * (r + 1)); } for (auto [l1, r1]: all){ int m1 = get(l1, r1); gp(m1, l1, r1); ll mn = inf; for (auto [l2, r2]: all1){ // f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1)); ll F = T1.get(r2); T1.add(l2, r2, 0, 1LL * m1 * (l2 - l1)); if (mn != inf) T1.chmin(l2, r2, m1, mn - 1LL * m1 * l1); mn = min(mn, F - 1LL * m1 * (r2 - l2)); } reverse(all1.begin(), all1.end()); mn = inf; for (auto [l2, r2]: all1){ // f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2)); ll F = T2.get(l2); T2.add(l2, r2, 0, 1LL * m1 * (r1 - r2)); if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1); mn = min(mn, F - 1LL * m1 * (r2 - l2)); } pp(m1, l1, r1); for (int i: f){ T1.add(i, i, 0, -T1.get(i)); ll mn = 1LL * m1 * (i - l1 + 1); if (i != l1) mn = min(mn, T1.get(i - 1) + m1); T1.add(i, i, 0, mn); } reverse(f.begin(), f.end()); for (int i: f){ T2.add(i, i, 0, -T2.get(i)); ll mn = 1LL * m1 * (r1 - i + 1); if (i != r1) mn = min(mn, T2.get(i + 1) + m1); T2.add(i, i, 0, mn); } } if (all.empty()) return; vector<int> x1, y1; for (auto [l1, r1]: all){ x1.pb(l1); y1.pb(r1); } int N = (int) all.size(), LG = log2(N); vector<vector<ll>> sp(N + 1, vector<ll>(LG + 1, inf)); for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff)); for (int j = 1; j <= LG; j++){ for (int i = 1; i + (1 << j) <= N + 1; i++){ sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]); } } auto gets = [&](int l, int r){ if (l > r) return inf; int k = log[r - l + 1]; return min(sp[l][k], sp[r - (1 << k) + 1][k]); }; for (auto [ql, qr, i]: qs[{l, r}]){ it1 = lower_bound(x1.begin(), x1.end(), ql); it2 = upper_bound(y1.begin(), y1.end(), qr); it2--; int i1 = (int) (it1 - x1.begin()), i2 = (int) (it2 - y1.begin()); out[i] = gets(i1 + 1, i2 + 1); if (out[i] != inf) out[i] += 1LL * m * (qr - ql); if (i1 > 0){ i1--; if (all[i1].ss >= ql){ out[i] = min(out[i], T2.get(ql) + 1LL * m * (qr - all[i1].ss)); } } if (it2 != prev(y1.end())){ i2++; if (all[i2].ff <= qr){ out[i] = min(out[i], T1.get(qr) + 1LL * m * (all[i2].ff - ql)); } } } }; build(1, n); vector<ll> ret; for (int i = 1; i <= q; i++) ret.pb(out[i]); return ret; }
#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...