제출 #15848

#제출 시각아이디문제언어결과실행 시간메모리
15848myungwoo휴가 (IOI14_holiday)C++14
30 / 100
1229 ms14092 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define MAXT 300005 typedef long long lld; static int N, S, T, K; static int A[MAXN], P[MAXN]; static lld D[MAXT]; struct Z{ int a, x; } B[MAXN]; struct NODE{ int cnt; lld sum; NODE *left, *right; } container[262144], *root; NODE *new_node() { NODE *ret = &container[K++]; ret->cnt = ret->sum = 0; ret->left = ret->right = 0; return ret; } void write(NODE *now, int s, int e, int n, int v) { if (n < s || e < n) return; if (s == e){ if (v >= 0){ now->cnt = 1; now->sum = v; }else{ now->cnt = now->sum = 0; } return; } if (!now->left) now->left = new_node(), now->right = new_node(); int m = (s+e)>>1; write(now->left, s, m, n, v); write(now->right, m+1, e, n, v); now->cnt = now->left->cnt + now->right->cnt; now->sum = now->left->sum + now->right->sum; } lld get_highest(NODE *now, int s, int e, int &left) { if (left <= 0) return 0; if (now->cnt <= left){ left -= now->cnt; return now->sum; } if (s == e) return 0; int m = (s+e)>>1; lld ret = get_highest(now->left, s, m, left); if (left > 0) ret += get_highest(now->right, m+1, e, left); return ret; } void calc(int l, int r, int s, int e) { if (s > e) return; int m = (s+e)>>1, t; D[m] = -1; for (int i=l;i<=r;i++){ write(root, 1, N, P[i], A[i]); int left = m-(i-S); if (left <= 0) break; lld sum = get_highest(root, 1, N, left); if (D[m] < sum) D[m] = sum, t = i; } if (s == e) return; for (int i=l;i<=r;i++) write(root, 1, N, P[i], -1); calc(l, t, s, m-1); for (int i=l;i<t;i++) write(root, 1, N, P[i], A[i]); calc(t, r, m+1, e); } lld proc() { for (int i=1;i<=N;i++) B[i].a = A[i], B[i].x = i; sort(B+1, B+N+1, [](const Z &a, const Z &b){ return a.a > b.a; }); for (int i=1;i<=N;i++) P[B[i].x] = i; K = 0; root = new_node(); calc(S, N, 1, T); return D[T]; } lld findMaxAttraction(int n, int start, int d, int arr[]) { N = n, S = start+1, T = d; for (int i=1;i<=N;i++) A[i] = arr[i-1]; lld ret = proc(); if (!start) return ret; reverse(A+1, A+N+1); S = N-S+1; return max(ret, proc()); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...