Submission #120783

#	Time	Username	Problem	Language	Result	Execution time	Memory
120783		youngyojun	Holiday (IOI14_holiday)	C++11	24 / 100	103 ms	65536 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 *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();
}

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