Submission #1145065

#TimeUsernameProblemLanguageResultExecution timeMemory
1145065Issa모임들 (IOI18_meetings)C++20
100 / 100
4338 ms307044 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e6 + 100; const int maxl = 20; int n; ll a[maxn]; int lg[maxn]; int p[maxl][maxn]; ll d[maxn * 4]; ll t[maxn * 4]; bool c[maxn * 4]; vector<ll> ans; vector<tuple<int, int, int>> g[maxn]; int C; int f(int i, int j){ if(C){ if(a[i] >= a[j]) return i; return j; } else{ if(a[i] > a[j]) return i; return j; } } int mx(int l, int r){ int k = lg[r - l + 1]; return f(p[k][l], p[k][r-(1<<k)+1]); } void pre(int v, ll a, ll b, bool C){ if(C) d[v] = t[v] = 0, c[v] = 1; d[v] += a; t[v] += b; } void push(int v, int tl, int tr){ if(tl == tr) return; int mid = (tl + tr) >> 1; pre(v<<1, d[v], t[v], c[v]); pre(v<<1|1, d[v] + (mid - tl + 1) * t[v], t[v], c[v]); d[v] = t[v] = c[v] = 0; } void upd(int l, int r, ll a, ll b, bool c, int v = 1, int tl = 1, int tr = n){ if(tl > r || tr < l) return; if(l <= tl && tr <= r) pre(v, a + (tl - l) * b, b, c); else{ push(v, tl, tr); int mid = (tl + tr) >> 1; upd(l, r, a, b, c, v<<1, tl, mid); upd(l, r, a, b, c, v<<1|1, mid+1, tr); } } ll get(int i, int v = 1, int tl = 1, int tr = n){ if(tl == tr) return d[v]; else{ push(v, tl, tr); int mid = (tl + tr) >> 1; if(i <= mid) return get(i, v<<1, tl, mid); else return get(i, v<<1|1, mid+1, tr); } } void calc(int l = 1, int r = n){ if(l > r) return; int v = mx(l, r); calc(l, v - 1); calc(v + 1, r); // cout << l << ' ' << r << ' ' << v << ":\n"; for(auto [i, tl, tr]: g[v]){ // cout << i << ' ' << tl << ' ' << tr << ' ' << get(tr) + (v - tl + 1) * a[v] << endl; ans[i] = min(ans[i], get(tr) + (v - tl + 1) * a[v]); } if(l < v) upd(v, v, get(v-1) + a[v], 0, 1); else upd(v, v, a[v], 0, 1); ll val = get(v), k = v; // cout << v << ' ' << l << ' ' << r << ":\n"; for(int tl = v + 1, tr = r; tl <= tr;){ int mid = (tl + tr) >> 1; // cout << mid << ' ' << val + (mid - v) * a[v] << ' ' << get(mid) + (v - l + 1) * a[v] << '\n'; if(val + (mid - v) * a[v] > get(mid) + (v - l + 1) * a[v]) tr = mid - 1; else tl = mid + 1, k = mid; } upd(v + 1, k, val + a[v], a[v], 1); upd(k + 1, r, (v - l + 1) * a[v], 0, 0); } void calc(vector<int> A, vector<int> L, vector<int> R){ fill(d, d + maxn * 4, 0); fill(t, t + maxn * 4, 0); fill(c, c + maxn * 4, 0); n = A.size(); for(int i = 1; i <= n; i++){ a[i] = A[i-1]; p[0][i] = i; g[i].clear(); if(i > 1) lg[i] = lg[i >> 1] + 1; } for(int k = 1; k < maxl; k++){ for(int i = 1; i + (1<<k) - 1 <= n; i++){ p[k][i] = f(p[k-1][i], p[k-1][i+(1<<(k-1))]); } } for(int i = 0; i < L.size(); i++){ g[mx(L[i], R[i])].push_back({i, L[i], R[i]}); } calc(); } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { ans = vector<ll>(L.size(), 1e18); for(int &x: L) x++; for(int &x: R) x++; calc(H, L, R); C = 1; reverse(H.begin(), H.end()); for(int &x: L) x = (n - x + 1); for(int &x: R) x = (n - x + 1); swap(L, R); calc(H, L, R); return ans; }
#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...