Submission #763998

#	Time	Username	Problem	Language	Result	Execution time	Memory
763998		SanguineChameleon	Holiday (IOI14_holiday)	C++17	100 / 100	2416 ms	19008 KiB

holiday

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

const long long inf = 1e18L + 20;
const int maxn = 1e5 + 20;

struct tree {
	vector<long long> *A;
	vector<long long> *B;
	int tree[maxn * 16];

	void build(int id, int lt, int rt) {
		tree[id] = -1;
		if (lt == rt) {
			return;
		}
		int mt = (lt + rt) / 2;
		build(id * 2, lt, mt);
		build(id * 2 + 1, mt + 1, rt);
	}

	long long eval(int off, int pos) {
		if (off == -1) {
			return -inf;
		}
		else {
			return (*A)[off] + (*B)[pos - off];
		}
	}

	void update(int id, int lt, int rt, int off, int ql, int qr) {
		if (qr < lt || ql > rt) {
			return;
		}
		if (lt == rt) {
			if (eval(off, lt) > eval(tree[id], lt)) {
				tree[id] = off;
			}
			return;
		}
		int mt = (lt + rt) / 2;
		if (ql <= lt && rt <= qr) {
			bool cmp1 = eval(off, lt) > eval(tree[id], lt);
			bool cmp2 = eval(off, mt) > eval(tree[id], mt);
			if (cmp1 != cmp2) {
				if (cmp2) {
					swap(tree[id], off);
				}
				update(id * 2, lt, mt, off, ql, qr);
			}
			else {
				if (cmp1) {
					swap(tree[id], off);
				}
				update(id * 2 + 1, mt + 1, rt, off, ql, qr);
			}
			return;
		}
		update(id * 2, lt, mt, off, ql, qr);
		update(id * 2 + 1, mt + 1, rt, off, ql, qr);
	}

	long long get(int id, int lt, int rt, int pos) {
		if (lt == rt) {
			return eval(tree[id], pos);
		}
		int mt = (lt + rt) / 2;
		if (pos <= mt) {
			return max(eval(tree[id], pos), get(id * 2, lt, mt, pos));
		}
		else {
			return max(eval(tree[id], pos), get(id * 2 + 1, mt + 1, rt, pos));
		}
	}

} T;

vector<long long> calc(vector<int> a) {
	int n = a.size();
	vector<long long> res(n * 2 + 1);
	if (n == 0) {
		return res;
	}
	if (n == 1) {
		res[2] = a[0];
		return res;
	}
	vector<int> left(a.begin(), a.begin() + n / 2);
	vector<int> right(a.begin() + n / 2, a.end());
	vector<long long> best_l = calc(left);
	vector<long long> best_r = calc(right);
	for (int i = 0; i <= (n / 2) * 2; i++) {
		res[i] = best_l[i];
	}
	for (int i = 0; i < n / 2; i++) {
		best_l[i] = -inf;
	}
	best_l[n / 2] = 0;
	sort(left.begin(), left.end(), greater<int>());
	for (int i = n / 2 + 1; i <= (n / 2) * 2; i++) {
		best_l[i] = best_l[i - 1] + left[i - n / 2 - 1];
	}
	T.A = &best_r;
	T.B = &best_l;
	T.build(1, n / 2, n * 2);
	for (int i = 0; i <= (n - n / 2) * 2; i++) {
		T.update(1, n / 2, n * 2, i, i + n / 2, i + (n / 2) * 2);
	}
	for (int i = n / 2; i <= n * 2; i++) {
		res[i] = max(res[i], T.get(1, n / 2, n * 2, i));
	}
	for (int i = 1; i <= n / 2; i++) {
		res[i] = max(res[i], res[i - 1]);
	}
	return res;
}

long long solve(int n, int start, int d, int attraction[]) {
	vector<int> left(start * 2);
	for (int i = 0; i < start; i++) {
		left[i * 2] = 0;
		left[i * 2 + 1] = attraction[start - 1 - i];
	}
	vector<int> right(n - 1 - start);
	for (int i = start + 1; i < n; i++) {
		right[i - start - 1] = attraction[i];
	}
	vector<long long> best_l = calc(left);
	vector<long long> best_r = calc(right);
	best_l.resize(d + 1);
	best_r.resize(d + 1);
	for (int i = 1; i <= d; i++) {
		best_l[i] = max(best_l[i], best_l[i - 1]);
		best_r[i] = max(best_r[i], best_r[i - 1]);
	}
	long long res = 0;
	for (int i = 0; i <= d; i++) {
		res = max(res, best_l[i] + best_r[d - i]);
	}
	for (int i = 0; i <= d - 1; i++) {
		res = max(res, best_l[i] + best_r[d - 1 - i] + attraction[start]);
	}
	return res;
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
	long long res1 = solve(n, start, d, attraction);
	for (int i = 0; i < n - 1 - i; i++) {
		swap(attraction[i], attraction[n - 1 - i]);
	}
	start = n - 1 - start;
	long long res2 = solve(n, start, d, attraction);
	return max(res1, res2);
}

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