제출 #242495

#제출 시각아이디문제언어결과실행 시간메모리
242495joseacaz휴가 (IOI14_holiday)C++17
0 / 100
1360 ms16760 KiB
#include"holiday.h" #include <bits/stdc++.h> #define pb push_back #define all(x) x.begin(), x.end() using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; struct Node { ll val = 0, active = 0; Node() { val = 0, active = 0; } Node(ll _v, ll _a) { val = _v; active = _a; } Node operator+ (const Node& _x) const { return {val + _x.val, active + _x.active}; } }; const int MAXN = 1e5 + 5; int N, a[MAXN], pos[MAXN], D; pll b[MAXN]; Node ST[4*MAXN]; bool cmp(pll _a, pll _b) { if(_a.first == _b.first) return _a.second < _b.second; return _a.first > _b.first; } void upd(int pos, int x, int node = 0, int l = 0, int r = N - 1) { if(r < pos || pos < l) return; if(l == r) { if(x) ST[node].val = b[l].first; else ST[node].val = 0; ST[node].active = x; return; } int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2; upd(pos, x, lchild, l, mid); upd(pos, x, rchild, mid + 1, r); ST[node] = ST[lchild] + ST[rchild]; } ll qry(int x, int node = 0, int l = 0, int r = N - 1) { if(x < 0) return -(1LL << 60LL); if(x == 0) return 0; if(l == r) return ST[node].val; int mid = (l+r)/2, lchild = 2*node + 1, rchild = 2*node + 2; if(ST[lchild].active <= x) return ST[lchild].val + qry(x - ST[lchild].active, rchild, mid + 1, r); else return qry(x, lchild, l, mid); } int start; pll f[3*MAXN], g[3*MAXN]; void solve(int l, int r, int l1, int r1) { if(l1 > r1) return; int days = (l1 + r1)/2; for(int i = l; i <= r; i++) upd(pos[i], 0); ll maxim = 0, tmp = l; for(int i = l; i <= r; i++) { upd(pos[i], 1); ll aux = qry(days-i+start); if(aux > maxim) { maxim = aux; tmp = i; } } f[days] = {tmp, maxim}; for(int i = l; i <= r; i++) upd(pos[i], 0); solve(l, f[days].first, l1, days - 1); for(int i = l; i < f[days].first; i++) upd(pos[i], 1); solve(f[days].first, r, days + 1, r1); } void solve2(int l, int r, int l1, int r1) { if(l1 > r1) return; int days = (l1 + r1)/2; for(int i = r; i >= l; i--) upd(pos[i], 0); ll maxim = 0, tmp = l; for(int i = r; i >= l; i--) { if(days-start+i < 0) break; upd(pos[i], 1); ll aux = qry(days-start+i); if(aux > maxim) { maxim = aux; tmp = i; } } g[days] = {tmp, maxim}; for(int i = r; i >= l; i--) upd(pos[i], 0); solve2(g[days].first, r, l1, days - 1); for(int i = g[days].first + 1; i <= r; i++) upd(pos[i], 1); solve2(l, g[days].first, days + 1, r1); } ll findMaxAttraction(int _n, int _start, int _d, int att[]) { N = _n; D = _d; start = _start; for(int i = 0; i < N; i++) { a[i] = att[i]; b[i] = {att[i], i}; } sort(b, b + N, cmp); for(int i = 0; i < N; i++) pos[b[i].second] = i; for(int i = 0; i < N; i++) upd(pos[i], 0); solve(start, N - 1, 0, 2*N + min(start, N - start - 1)); for(int i = 0; i < N; i++) upd(pos[i], 0); solve2(0, start - 1, 0, 2*N + min(start, N - start - 1)); ll ans = 0; for(int i = 0; i <= D; i++) { if(D - (f[i].first-start) - i >= 0) ans = max(ans, f[i].second + g[D-(f[i].first-start)-i].second); if(D - (start-g[i].first) - i >= 0) ans = max(ans, g[i].second + f[D-(start-g[i].first)-i].second); } 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...