Submission #467333

#TimeUsernameProblemLanguageResultExecution timeMemory
467333apostoldaniel854Holiday (IOI14_holiday)C++14
93 / 100
1002 ms8120 KiB
#include "holiday.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define dbg(x) cerr << #x << " " << x << "\n" const int MAX_N = 1e5; pair <int, int> a[1 + MAX_N]; class switch_max { public: struct node_state { int cnt_on; ll sum; }; vector <node_state> seg; int n; switch_max(int n) { this->n = n; seg.resize(1 + 4 * n, {0, 0}); } node_state join(node_state L, node_state R) { node_state RES; RES.cnt_on = L.cnt_on + R.cnt_on; RES.sum = L.sum + R.sum; return RES; } void treat_leaf(int node, bool state, int value) { seg[node] = {state, value}; }; void change(int node, int lb, int rb, int pos, bool state, int value) { if (lb == rb) { treat_leaf(node, state, value); return; } int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1; if (pos <= mid) change(lnode, lb, mid, pos, state, value); else change(rnode, mid + 1, rb, pos, state, value); seg[node] = join(seg[lnode], seg[rnode]); } ll solve(int node, int lb, int rb, int k) { if (seg[node].cnt_on <= k) return seg[node].sum; int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1; if (seg[rnode].cnt_on >= k) return solve(rnode, mid + 1, rb, k); return seg[rnode].sum + solve(lnode, lb, mid, k - seg[rnode].cnt_on); } void turn_on(int pos) { change(1, 1, n, pos, true, a[pos].first); } void turn_off(int pos) { change(1, 1, n, pos, false, 0); } ll solve(int k) { return solve(1, 1, n, k); } }; ll ans; int mp[1 + MAX_N]; int pivot; void divide(int lb, int rb, int bestl, int bestr, switch_max &solver, int d) { if (lb > rb || bestl > bestr) return; int mid = (lb + rb) / 2; for (int i = mid; i <= rb; i++) solver.turn_on(mp[i]); int bestmid = bestl; ll bestvalue = -1; for (int i = bestl; i <= bestr; i++) { int to_grab = d - (pivot - mid) - (i - mid); if (to_grab > 0) { solver.turn_on(mp[i]); ll cnt = solver.solve(to_grab); if (cnt > bestvalue) { bestvalue = cnt; bestmid = i; } } } ans = max(ans, bestvalue); for (int i = bestl + 1; i <= bestr; i++) solver.turn_off(mp[i]); divide(lb, mid - 1, bestl, bestmid, solver, d); for (int i = mid; i <= rb; i++) solver.turn_off(mp[i]); for (int i = bestl; i < bestmid; i++) solver.turn_on(mp[i]); divide(mid + 1, rb, bestmid, bestr, solver, d); for (int i = bestl; i < bestmid; i++) solver.turn_off(mp[i]); } /** 100 0 150 4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13 **/ long long int findMaxAttraction(int n, int start, int d, int attraction[]) { start++; for (int i = 1; i <= n; i++) a[i] = {attraction[i - 1], i}; sort (a + 1, a + n + 1); switch_max solver(n); for (int i = 1; i <= n; i++) mp[a[i].second] = i; pivot = start; divide(1, start, start, n, solver, d); for (int i = 1; i <= n; i++) mp[n - a[i].second + 1] = i; pivot = n - start + 1; divide(1, n - start + 1, n - start + 1, n, solver, d); 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...