Submission #1092942

#TimeUsernameProblemLanguageResultExecution timeMemory
1092942shivansh0809Holiday (IOI14_holiday)C++17
24 / 100
93 ms65536 KiB
#include "holiday.h" #include <bits/stdc++.h> using namespace std; struct PersistentSegTree { // find_kth returns the kth smallest element in the array in [l, r) struct Vertex { Vertex *l, *r; int sum; long long k_sum; Vertex(int val) : l(nullptr), r(nullptr), sum(val), k_sum(0) {} Vertex(int val, long long k_sum) : l(nullptr), r(nullptr), sum(val), k_sum(k_sum) {} Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0), k_sum(0) { if (l) sum += l->sum, k_sum += l->k_sum; if (r) sum += r->sum, k_sum += r->k_sum; } }; vector<Vertex *> roots; map<int, pair<int, int>> compress; int n; PersistentSegTree(vector<int> v) : n(v.size()) { int tl = 0, tr = n; vector<pair<int, int>> sort_v; for (int i = 0; i < n; i++) sort_v.push_back({v[i], i}); sort(sort_v.begin(), sort_v.end(), greater<pair<int, int>>()); vector<int> idx(n); for (int i = 0; i < n; i++) compress[i] = sort_v[i], idx[sort_v[i].second] = i; roots.push_back(build(tl, tr)); for (int i = 0; i < n; i++) roots.push_back(update(roots.back(), tl, tr, idx[i])); } Vertex *build(int tl, int tr) { if (tl == tr) return new Vertex(0, 0); int tm = (tl + tr) / 2; return new Vertex(build(tl, tm), build(tm + 1, tr)); } Vertex *update(Vertex *v, int tl, int tr, int pos) { if (tl == tr) return new Vertex(v->sum + 1, v->k_sum + compress[pos].first); int tm = (tl + tr) / 2; if (pos <= tm) return new Vertex(update(v->l, tl, tm, pos), v->r); else return new Vertex(v->l, update(v->r, tm + 1, tr, pos)); } long long find_kth(Vertex *vl, Vertex *vr, int tl, int tr, int k) { if (tl == tr) return vr->k_sum - vl->k_sum; int tm = (tl + tr) / 2; int left_count = vr->l->sum - vl->l->sum; if (left_count >= k) return find_kth(vl->l, vr->l, tl, tm, k); return vr->l->k_sum - vl->l->k_sum + find_kth(vl->r, vr->r, tm + 1, tr, k - left_count); } long long find_kth(int l, int r, int k) { return find_kth(roots[l], roots[r], 0, n, k); } }; long long int findMaxAttraction(int n, int start, int d, int attraction[]) { long long int ans = 0; PersistentSegTree pst(vector<int>(attraction, attraction + n)); function<long long(int, int)> C1 = [&](int k, int mid) -> long long { int days_rem = d - (mid - k + start - k); if (days_rem <= 0) return 0; return pst.find_kth(k, mid + 1, days_rem); // return mid - k; }; function<long long(int, int)> C2 = [&](int mid, int k) -> long long { int days_rem = d - (k - mid + k - start); if (days_rem <= 0) return 0; return pst.find_kth(mid, k + 1, days_rem); // return k - mid; }; function<void(int, int, int, int)> dncg = [&](int l, int r, int optl, int optr) { if (l > r) return; int mid = (l + r) >> 1; pair<long long, int> best = {-1, -1}; for (int k = optl; k <= min(mid, optr); k++) best = max(best, {C1(k, mid), k}); // debug(dp, best, ndp); // debug(ans, best, mid); ans = max(best.first, ans); int opt = best.second; dncg(l, mid - 1, optl, opt); dncg(mid + 1, r, opt, optr); }; function<void(int, int, int, int)> dncs = [&](int l, int r, int optl, int optr) { if (l > r) return; int mid = (l + r) >> 1; pair<long long, int> best = {-1, -1}; for (int k = optr; k >= max(mid, optl); k--) best = max(best, {C2(mid, k), k}); // debug(dp, best, ndp); // debug(ans, best, mid); ans = max(best.first, ans); int opt = best.second; dncs(l, mid - 1, optl, opt); dncs(mid + 1, r, opt, optr); }; if (d == 0) return 0; ans = attraction[start]; dncg(start + 1, n - 1, 0, start); dncs(0, start - 1, start, n - 1); 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...