Submission #977647

#TimeUsernameProblemLanguageResultExecution timeMemory
977647happypotatoMeetings (IOI18_meetings)C++17
36 / 100
600 ms209048 KiB
#include "meetings.h" #include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back struct info { int ans, lmax, rmax; bool full; info(int x = 0): ans(x), lmax(x), rmax(x), full(x) {}; }; info merge(info lhs, info rhs) { info res; res.lmax = (lhs.full ? lhs.lmax + rhs.lmax : lhs.lmax); res.rmax = (rhs.full ? rhs.rmax + lhs.rmax : rhs.rmax); res.ans = max({lhs.ans, rhs.ans, lhs.rmax + rhs.lmax}); res.full = (lhs.full && rhs.full); return res; } const int mxN = 1e5 + 10; info seg[4 * mxN]; bool a[mxN]; int n; void build(int l = 0, int r = n - 1, int idx = 1) { if (l == r) { seg[idx] = info(!a[l]); return; } int mid = (l + r) >> 1; build(l, mid, (idx << 1)); build(mid + 1, r, (idx << 1) | 1); seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]); } info query(int tl, int tr, int l = 0, int r = n - 1, int idx = 1) { if (tl <= l && r <= tr) return seg[idx]; int mid = (l + r) >> 1; if (tr <= mid) return query(tl, tr, l, mid, (idx << 1)); if (tl > mid) return query(tl, tr, mid + 1, r, (idx << 1) | 1); return merge(query(tl, tr, l, mid, (idx << 1)), query(tl, tr, mid + 1, r, (idx << 1) | 1)); } vector<long long> minimum_costs(vector<int32_t> H, vector<int32_t> L, vector<int32_t> R) { n = H.size(); if (n <= 5000) { vector<int> ans; int precomp[n][n]; for (int i = 0; i < n; i++) { precomp[i][i] = H[i]; int maxi; maxi = H[i]; for (int j = i - 1; j >= 0; j--) { maxi = max(maxi, 1LL * H[j]); precomp[i][j] = precomp[i][j + 1] + maxi; } maxi = H[i]; for (int j = i + 1; j < n; j++) { maxi = max(maxi, 1LL * H[j]); precomp[i][j] = precomp[i][j - 1] + maxi; } } for (int i = 0; i < (int)(L.size()); i++) { int l = L[i], r = R[i]; int cur = 1e18; for (int j = l; j <= r; j++) { cur = min(cur, precomp[j][l] + precomp[j][r] - precomp[j][j]); } // cerr << l << ' ' << r << ' ' << cur << endl; ans.pb(cur); } return ans; } for (int i = 0; i < n; i++) a[i] = (H[i] == 2); build(); vector<int> ans; for (int i = 0; i < (int)(L.size()); i++) { // cerr << L[i] << ' ' << R[i] << ' ' << query(L[i], R[i]).ans << endl; ans.pb(2LL * (R[i] - L[i] + 1) - query(L[i], R[i]).ans); } return ans; } #undef int
#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...