Submission #362762

#	Time	Username	Problem	Language	Result	Execution time	Memory
362762		hoaphat1	Holiday (IOI14_holiday)	C++14	Compilation error	0 ms	0 KiB

holiday

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

struct node {
	long long val = 0;
	int cnt = 0;
	int lef = -1, rig = -1;
};

const int N = (int) 1e5 + 3;
node st[31 * N];
int cnt = 0;

void modify(int&id, int l, int r, int pos, int val) {
	if (id == -1) id = ++cnt;
	if (l == r) {
		st[id].val += pos * val;
		st[id].cnt += val;
		return ;
	}
	int mid = l + r >> 1;
	if (pos <= mid) modify(st[id].lef, l, mid, pos, val);
	else modify(st[id].rig, mid + 1, r, pos, val);
	st[id].val = st[id].cnt = 0;
	if (st[id].lef != -1) {
		st[id].val += st[st[id].lef].val;
		st[id].cnt += st[st[id].lef].cnt;
	}
	if (st[id].rig != -1) {
		st[id].val += st[st[id].rig].val;
		st[id].cnt += st[st[id].rig].cnt;
	}
}
long long get(int id, int l, int r, int& num) {
	if (id == -1 || !num) return 0;
	if (num >= st[id].cnt) {
		num -= st[id].cnt;
		return st[id].val;
	}
	if (l == r) return 0;
	int mid = l + r >> 1;
	return get(st[id].rig, mid + 1, r, num) + get(st[id].lef, l, mid, num);
}

long long findMaxAttraction(int n, int s, int d, int a[]) {
	long long ans = 0;
  int L = 0, R = -1;
  const int maxN = (int) 1e9;
  int root = 0;
  auto add = [&](int id) {
  	modify(root, 0, maxN, a[id], 1);
	};
	auto del = [&](int id) {
		modify(root, 0, maxN, a[id], -1);
	};
  auto moveL = [&](int l) {
  	while (L < l) del(L++);
  	while (L > l) add(--L);
	};
	auto moveR = [&](int r) {
		while (R < r) add(++R);
		while (R > r) del(R--);
	};
	function<void(int, int, int, int)> solve = [&](int l, int r, int L, int R) {
		if (l > r) return ;
		int mid = l + r >> 1;
		int pos = -1;
		moveR(L);
		moveL(mid);
		long long val = -1;
		for (int i = L; i <= R; i++) {
			moveR(i);
			int lim = d - min(s - mid, i - s) - (i - mid);
			long long now = get(0, 0, maxN, lim);
			if (val < now) {
				val = now;
				pos = i;
			}
		}
		ans = max(ans, val);
		assert(pos != -1);
		solve(l, mid - 1, L, pos);
		solve(mid + 1, r, pos, R);
	};
	solve(max(0, s - d), s, s, min(n - 1, s + d));
	return ans;
}

Compilation message (stderr)

Compilation timeout while compiling holiday