Submission #102439

#	Time	Username	Problem	Language	Result	Execution time	Memory
102439		eriksuenderhauf	Holiday (IOI14_holiday)	C++11	100 / 100	3111 ms	15144 KiB

holiday

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "holiday.h"
//#include "grader.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 9;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const double eps = 1e-9;
struct node
{
	ll sum; int act;
} seg[MAXN*4];
ll arr[MAXN], ind[MAXN], rev[MAXN];
ll indR[MAXN], indL[MAXN];
ll vR[MAXN], vL[MAXN];
int n;

node operator +(node &lhs, const node &rhs) {
	return {lhs.sum + rhs.sum, lhs.act + rhs.act};
}

node operator +=(node &lhs, const node &rhs) {
	return lhs = lhs + rhs;
}

void build(int l, int r, int k) {
	if (l == r) {
		seg[k] = {0, 0};
		return;
	}
	int m = (l + r) / 2;
	build(l, m, k*2);
	build(m+1, r, k*2+1);
	seg[k] = seg[k*2] + seg[k*2+1];
}

void upd(int l, int r, int k, int a, int v) {
	if (r < a || a < l) return;
	if (a <= l && r <= a) {
		seg[k].act = v;
		if (seg[k].act == 1)
			seg[k].sum = arr[l];
		else
			seg[k].sum = 0;
		return;
	}
	int m = (l + r) / 2;
	upd(l, m, k*2, a, v);
	upd(m+1, r, k*2+1, a, v);
	seg[k] = seg[k*2] + seg[k*2+1];
}

node qry(int l, int r, int k, int cnt) {
	if (seg[k].act == 0) return {0, 0};
	if (seg[k].act <= cnt) return seg[k];
	int m = (l + r) / 2;
	node lhs = qry(l, m, k*2, cnt);
	if (lhs.act >= cnt) return lhs;
	return lhs + qry(m + 1, r, k*2+1, cnt - lhs.act);
}

void dfsL(int l, int r, int oL, int oR, int st) {
	if (l > r || oR < 0 || oL < 0) return;
	int m = (l + r) / 2;
	indL[m] = oL;
	vL[m] = 0;
	for (int i = oL; i >= oR; i--) {
		if (m - (st - i) < 0) break;
		upd(0, n - 1, 1, rev[i], 1);
		ll val = qry(0, n - 1, 1, m - (st - i)).sum;
		if (val > vL[m]) {
			vL[m] = val;
			indL[m] = i;
		}
	}
	for (int i = indL[m]; i >= oR; i--) upd(0, n - 1, 1, rev[i], 0);
	dfsL(m + 1, r, indL[m], oR, st);
	for (int i = oL; i >= oR; i--) upd(0, n - 1, 1, rev[i], 0);
	dfsL(l, m - 1, oL, indL[m], st);
}

void dfsR(int l, int r, int oL, int oR, int st) {
	if (l > r || oL >= n || oR >= n) return;
	int m = (l + r) / 2;
	indR[m] = oL;
	vR[m] = 0;
	for (int i = oL; i <= oR; i++) {
		if (m - (i - st) < 0) break;
		upd(0, n - 1, 1, rev[i], 1);
		ll val = qry(0, n - 1, 1, m - (i - st)).sum;
		if (val > vR[m]) {
			vR[m] = val;
			indR[m] = i;
		}
	}
	for (int i = indR[m]; i <= oR; i++) upd(0, n - 1, 1, rev[i], 0);
	dfsR(m + 1, r, indR[m], oR, st);
	for (int i = oL; i <= oR; i++) upd(0, n - 1, 1, rev[i], 0);
	dfsR(l, m - 1, oL, indR[m], st);
}

ll findMaxAttraction(int N, int start, int d, int attraction[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		ind[i] = i;
		arr[i] = attraction[i];
	}
	sort(ind, ind + n, [](int l, int r) {
		return arr[l] > arr[r];
	});
	sort(arr, arr + n, [](int l, int r) {
		return l > r;
	});
	for (int i = 0; i < n; i++)
		rev[ind[i]] = i;
	build(0, n - 1, 1);
	dfsR(1, d, start, n - 1, start);
	build(0, n - 1, 1);
	dfsL(1, d, start - 1, 0, start - 1);
	ll ans = 0;
	for (int i = 1; i <= d; i++) {
		ll tmp = vR[i];
		if (d - i - (indR[i] - start + 1) >= 0)
			tmp += vL[d - i - (indR[i] - start + 1)];
		ans = max(ans, tmp);
	}
	build(0, n - 1, 1);
	dfsR(1, d, start + 1, n - 1, start + 1);
	build(0, n - 1, 1);
	dfsL(1, d, start, 0, start);
	for (int i = 1; i <= d; i++) {
		ll tmp = vL[i];
		if (d - i - (start - indL[i] + 1) >= 0)
			tmp += vR[d - i - (start - indL[i] + 1)];
		ans = max(ans, tmp);
	}
	return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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