Submission #145915

#TimeUsernameProblemLanguageResultExecution timeMemory
145915MinnakhmetovMeetings (IOI18_meetings)C++14
19 / 100
777 ms349492 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define all(aaa) aaa.begin(), aaa.end() const ll INF = 1e18; const int N1 = 5005, N2 = 1e5 + 5, K = 21; ll lp[N1][N1], rp[N1][N1], seg_val[K][N2]; int n, q; vector<int> a, occ[K]; vector<ll> slow(vector<int> L, vector<int> R) { for (int i = 0; i < n; i++) { ll cur = 0; int mx = a[i]; for (int j = i - 1; j >= 0; j--) { mx = max(mx, a[j]); cur += mx; lp[j][i] = cur; } cur = 0; mx = a[i]; for (int j = i + 1; j < n; j++) { mx = max(mx, a[j]); cur += mx; rp[i][j] = cur; } } vector<ll> ans(q); for (int i = 0; i < q; i++) { ll mn = INF; for (int j = L[i]; j <= R[i]; j++) { mn = min(mn, lp[L[i]][j] + rp[j][R[i]] + a[j]); } ans[i] = mn; } return ans; } struct ST { ll t[N2 * 4]; void build(int v, int L, int R, ll val[N2]) { if (L == R) { t[v] = val[L]; } else { int m = (L + R) >> 1; build(v * 2, L, m, val); build(v * 2 + 1, m + 1, R, val); t[v] = min(t[v * 2], t[v * 2 + 1]); } } ll que(int l, int r, int v, int L, int R) { if (l > r) return INF; if (l == L && r == R) { return t[v]; } int m = (L + R) >> 1; return min(que(l, min(m, r), v * 2, L, m), que(max(m + 1, l), r, v * 2 + 1, m + 1, R)); } } tr[K]; ll build(int x, int l, int r) { if (l > r) return 0; int fo = lower_bound(all(occ[x]), l) - occ[x].begin(), lo = upper_bound(all(occ[x]), r) - occ[x].begin() - 1; if (fo > lo) return build(x - 1, l, r) - (r - l + 1); ll mn = min(build(x - 1, l, occ[x][fo] - 1), build(x - 1, occ[x][lo] + 1, r)); for (int i = fo; i < lo; i++) { ll res = build(x - 1, occ[x][fo] + 1, occ[x][lo] - 1); seg_val[x][i] = res; mn = min(mn, res); } // cout << x << " " << l << " " << r << " " << mn + (r - l + 1) * x << "\n"; return mn - (r - l + 1); } ll que(int x, int l, int r) { if (l > r) return 0; int fo = lower_bound(all(occ[x]), l) - occ[x].begin(), lo = upper_bound(all(occ[x]), r) - occ[x].begin() - 1; if (fo > lo) return que(x - 1, l, r) - (r - l + 1); ll mn = min(que(x - 1, l, occ[x][fo] - 1), que(x - 1, occ[x][lo] + 1, r)); mn = min(mn, tr[x].que(fo, lo - 1, 1, 0, occ[x].size() - 1)); // cout << x << " " << l << " " << r << " " << mn + (r - l + 1) * x << "\n"; return mn - (r - l + 1); } vector<ll> solveWhenLessThan20(vector<int> L, vector<int> R) { vector<ll> ans(q, 0); for (int i = 0; i < K; i++) { occ[i].push_back(-1); } for (int i = 0; i < n; i++) { occ[a[i]].push_back(i); } for (int i = 0; i < K; i++) { occ[i].push_back(n); fill(seg_val[i], seg_val[i] + occ[i].size(), INF); } build(K - 1, 0, n - 1); for (int i = 0; i < K; i++) { tr[i].build(1, 0, occ[i].size() - 1, seg_val[i]); } for (int i = 0; i < q; i++) { ans[i] = que(K - 1, L[i], R[i]) + (R[i] - L[i] + 1) * K; } return ans; } std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) { a = H; n = a.size(), q = L.size(); if (n < N1 && q < N1) { return slow(L, R); } return solveWhenLessThan20(L, R); }
#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...