제출 #120783

#제출 시각아이디문제언어결과실행 시간메모리
120783youngyojun휴가 (IOI14_holiday)C++11
24 / 100
103 ms65536 KiB
#include "holiday.h" #include <bits/stdc++.h> #define upmax(a,b) (a)=max((a),(b)) #define INFLL (0x3f3f3f3f3f3f3f3fll) using namespace std; typedef long long ll; const int MAXN = 100055; struct NOD { NOD *l, *r; ll sum; int cnt; NOD(); } *nil, *pst[MAXN]; NOD :: NOD() { l = r = nil; sum = cnt = 0; } int A[MAXN], AO[MAXN], ARO[MAXN]; ll Ans; int N, X, L; void makeTree(NOD *bf, NOD *nw, int s, int e, int x, int r) { nw -> cnt = bf -> cnt + 1; nw -> sum = bf -> sum + r; if(s == e) return; int m = (s+e) >> 1; if(x <= m) { nw -> r = bf -> r; nw -> l = new NOD(); makeTree(bf -> l, nw -> l, s, m, x, r); } else { nw -> l = bf -> l; nw -> r = new NOD(); makeTree(bf -> r, nw -> r, m+1, e, x, r); } } ll get(NOD *bf, NOD *nw, int x) { if(!x) return 0; if(nw->cnt - bf->cnt == x) return nw->sum - bf->sum; int lc = nw->l->cnt - bf->l->cnt; if(x <= lc) return get(bf->l, nw->l, x); return (nw->l->sum - bf->l->sum) + get(bf->r, nw->r, x-lc); } ll get(int s, int e, int x) { return get(pst[s-1], pst[e], x); } void f(int s, int e, int p, int q) { if(s > e || p > q) return; int m = (s+e) >> 1; ll hc = -INFLL; int hi = -1; for(int x = p, xe = min({N, (L+X+m)/2, q}); x <= xe; x++) { ll t = get(m, x, min(x-m+1, L-(x+x-m-X))); if(t <= hc) continue; hc = t; hi = x; } upmax(Ans, hc); f(s, m-1, p, hi); f(m+1, e, hi, q); } ll getAns() { nil = new NOD(); nil->l = nil->r = nil; nil->sum = nil->cnt = 0; iota(AO, AO+N+1, 0); sort(AO+1, AO+N+1, [&](int a, int b) { return A[a] > A[b]; }); for(int i = 1; i <= N; i++) ARO[AO[i]] = i; pst[0] = nil; for(int i = 1; i <= N; i++) { pst[i] = new NOD(); makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]); } f(max(1, X-L), X, X, N); X = N+1-X; reverse(A+1, A+N+1); iota(AO, AO+N+1, 0); sort(AO+1, AO+N+1, [&](int a, int b) { return A[a] > A[b]; }); for(int i = 1; i <= N; i++) ARO[AO[i]] = i; for(int i = 1; i <= N; i++) { pst[i] = new NOD(); makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]); } f(max(1, X-L), X, X, N); return Ans; } long long int findMaxAttraction(int n, int start, int d, int attraction[]) { ::N = n; ::X = start + 1; ::L = d; for(int i = 0; i < n; i++) ::A[i+1] = attraction[i]; return getAns(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...