제출 #564380

#제출 시각아이디문제언어결과실행 시간메모리
564380thecodingwizard휴가 (IOI14_holiday)C++17
0 / 100
541 ms11560 KiB
#include <bits/stdc++.h> #include "holiday.h" using namespace std; using ll = long long; #define f first #define s second #define ii pair<int, int> #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() const int maxn = 100000; int n, start, d; int stIndex[maxn]; struct node { ll val; int initVal; int ct; } st[maxn*4]; void buildST(int attraction[]) { vector<ii> attractions; for (int i = 0; i < n; i++) { attractions.pb(mp(attraction[i], i)); } sort(all(attractions)); reverse(all(attractions)); int i = 0; for (auto x : attractions) { stIndex[x.s] = i; i++; } auto build = [&](int p, int i, int j, const auto &build)->void { if (i == j) { st[p] = node{0, attractions[i].f, 0}; } else { build(p*2, i, (i+j)/2, build); build(p*2+1, (i+j)/2+1, j, build); st[p] = node{0,-1,0}; } }; build(1, 0, n-1, build); } void upd(int p, int i, int j, int k, bool isActive) { if (i > k || j < k) return; if (i == j && i == k) { st[p].val = isActive ? st[p].initVal : 0; st[p].ct = isActive; } else { upd(p*2, i, (i+j)/2, k, isActive); upd(p*2+1, (i+j)/2+1, j, k, isActive); st[p].val = st[p*2].val + st[p*2+1].val; st[p].ct = st[p*2].ct + st[p*2+1].ct; } } ll qry(int p, int i, int j, int k) { if (st[p].ct <= k) return st[p].val; if (i == j) return k == 0 ? 0 : st[p].val; if (st[p*2].ct >= k) return qry(p*2, i, (i+j)/2, k); return st[p*2].val + qry(p*2+1, (i+j)/2+1, j, k - st[p*2].ct); } vector<ll> oneWayLeft(3*maxn), oneWayRight(3*maxn); void compute(int l, int r, int optl, int optr, vector<ll> &dp) { if (l > r) return; int mid = (l+r)/2; ll best = -1; int bestTransition = -1; for (int k = optl; k <= optr; k++) { upd(1, 0, n-1, stIndex[k], 1); int stepsRemaining = d - k - start; ll val = qry(1, 0, n-1, stepsRemaining); if (best < val) { best = val; bestTransition = k; } } dp[mid] = best; for (int k = bestTransition+1; k <= optr; k++) { upd(1, 0, n-1, stIndex[k], 0); } compute(mid+1, r, bestTransition, optr, dp); for (int k = optl; k <= bestTransition; k++) { upd(1, 0, n-1, stIndex[k], 0); } compute(l, mid-1, optl, bestTransition, dp); } long long int findMaxAttraction(int N, int Start, int D, int attraction[]) { assert(Start == 0); n = N, start = Start, d = D; buildST(attraction); compute(0, d, 0, n-1, oneWayRight); cout << oneWayRight[d] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...