Submission #550710

#	Time	Username	Problem	Language	Result	Execution time	Memory
550710		sidon	Holiday (IOI14_holiday)	C++17	100 / 100	251 ms	2704 KiB

holiday

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int Z = 1e5;

int n, *a, d, o, C[Z], G[Z+1], L = 1, R;
i64 F[Z+1], ans;

void add(const int &j, const int &s) {
	for(int i = 1 + C[j]; i <= n; i += i&-i) {
		G[i] += s;
		F[i] += s * a[j];
	}
}

i64 get(int v) {
	int i {}; i64 res {};
	for(int j = 1<<17; j /= 2; ) if(i + j <= n && G[i + j] <= v) {
		i += j;
		res += F[i];
		v -= G[i];
	}
	return res;
}

void reset(const int &l, const int &r) {
	while(L > l) add(--L, +1);
	while(R < r) add(++R, +1);
	while(L < l) add(L++, -1);
	while(R > r) add(R--, -1);
}

void dfs(int li, int ri, int lv, int rv) {
	if(ri <= li) return;
	int mi = (li + ri) / 2;
	i64 best {};

	int sv = max(mi, lv), mv = sv;
	reset(mi, sv - 1);
	for(int v = sv; v < rv; ++v) {
		add(++R, 1);
		i64 cur = get(max((int)(0), d - min(abs(o - mi), abs(o - v)) - (v - mi)));
		if(cur > best) best = cur, mv = v;
	}
	ans = max(ans, best);

	dfs(li, mi, lv, mv + 1);
	dfs(mi + 1, ri, mv, rv);
}

i64 findMaxAttraction(int _n, int start, int _d, int _a[]) {
	a = _a, n = _n, d = _d, o = start;
	int byA[n];
	iota(byA, byA + n, 0);
	sort(byA, byA + n, [&](const int &i, const int &j) {
		return a[i] > a[j];
	});
	for(int i = 0; i < n; ++i) C[byA[i]] = i;
	dfs(0, n, 0, n);
	return ans;
}

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