Submission #120785

#	Time	Username	Problem	Language	Result	Execution time	Memory
120785		youngyojun	Holiday (IOI14_holiday)	C++11	100 / 100	306 ms	45448 KiB

holiday

#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() : sum(0), cnt(0), l(0), r(0) {}

	ll sum;
	int cnt, l, r;
} arr[MAXN*18]; int arrn;
int newNOD() { return ++arrn; }
int pst[MAXN];

int A[MAXN], AO[MAXN], ARO[MAXN];

ll Ans;
int N, X, L;

void makeTree(int bf, int nw, int s, int e, int x, int r) {
	arr[nw].cnt = arr[bf].cnt + 1;
	arr[nw].sum = arr[bf].sum + r;
	if(s == e) return;
	int m = (s+e) >> 1;
	if(x <= m) {
		arr[nw].r = arr[bf].r;
		arr[nw].l = newNOD();
		makeTree(arr[bf].l, arr[nw].l, s, m, x, r);
	} else {
		arr[nw].l = arr[bf].l;
		arr[nw].r = newNOD();
		makeTree(arr[bf].r, arr[nw].r, m+1, e, x, r);
	}
}

ll _get(int bf, int nw, int x) {
	if(!x) return 0;
	if(arr[nw].cnt - arr[bf].cnt == x) return arr[nw].sum - arr[bf].sum;
	int lc = arr[arr[nw].l].cnt - arr[arr[bf].l].cnt;
	if(x <= lc) return _get(arr[bf].l, arr[nw].l, x);
	return (arr[arr[nw].l].sum - arr[arr[bf].l].sum) + _get(arr[bf].r, arr[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() {
	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] = newNOD();
		makeTree(pst[i-1], pst[i], 1, N, ARO[i], A[i]);
	}

	f(max(1, X-L), X, X, N);

	arrn = 0;

	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] = newNOD();
		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();
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53