Submission #15849

#	Time	Username	Problem	Language	Result	Execution time	Memory
15849		myungwoo	Holiday (IOI14_holiday)	C++14	30 / 100	1234 ms	14096 KiB

holiday

#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);
}

void get(NODE *now, int s, int e, int l, int r, int &cnt, lld &sum)
{
	if (e < l || r < s) return;
	if (l <= s && e <= r){
		cnt += now->cnt;
		sum += now->sum;
		return;
	}
	if (!now->left) return;
	int m = (s+e)>>1;
	get(now->left, s, m, l, r, cnt, sum);
	get(now->right, m+1, e, l, r, cnt, sum);
}

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);
	K = 0; root = new_node();
	lld ret = D[T];
	for (int i=1;i<=N;i++) if (B[i].x < S){
		write(root, 1, N, B[i].x, B[i].a);
		int cnt = 0; lld sum = 0;
		get(root, 1, N, B[i].x, S, cnt, sum);
		int left = T - (S-B[i].x) * 2 - cnt;
		if (left < 0) continue;
		ret = max(ret, sum + D[left]);
	}
	return ret;
}

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

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