Submission #58661

#	Time	Username	Problem	Language	Result	Execution time	Memory
58661		aome	Holiday (IOI14_holiday)	C++17	100 / 100	622 ms	56144 KiB

holiday

#include "holiday.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, d, start;
int a[N];
int ver[N];

struct SegmentTree {
	struct Node {
		int l, r;
		int cnt;
		long long sum;
		
		Node() { cnt = sum = 0; }
	};

	int num;
	Node T[N * 20];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (l == r) return;
		T[i].l = ++num;
		build(T[i].l, l, mid);
		T[i].r = ++num;
		build(T[i].r, mid + 1, r);
	}

	void upd(int i, int j, int l, int r, int p, int x) {
		T[i].cnt = T[j].cnt + 1, T[i].sum = T[j].sum + x;
		if (l == r) return;
		if (mid >= p) {
			T[i].l = ++num, T[i].r = T[j].r;
			upd(T[i].l, T[j].l, l, mid, p, x);
		}
		else {
			T[i].l = T[j].l, T[i].r = ++num;
			upd(T[i].r, T[j].r, mid + 1, r, p, x);
		}
	}

	long long get(int i, int j, int k) {
		int cnt;
		long long sum;
		long long ret = 0;
		while (k) {
			cnt = T[i].cnt - T[j].cnt;
			sum = T[i].sum - T[j].sum;
			if (k == cnt) {
				k -= cnt, ret += sum; break;
			}
			cnt = T[T[i].r].cnt - T[T[j].r].cnt;
			sum = T[T[i].r].sum - T[T[j].r].sum;
			if (k >= cnt) {
				k -= cnt, ret += sum;
				i = T[i].l, j = T[j].l; 
			}
			else {
				i = T[i].r, j = T[j].r;
			}
		}
		return ret;
	}

	#undef mid

} IT;

long long res;

void go(int l, int r, int L, int R) {
	if (l > r) return;
	int mid = (l + r) >> 1;
	int pos = 0;
	long long opt = 0;
	for (int i = L; i <= R; ++i) {
		int tmp = d - (mid - start) - (mid - i);
		tmp = max(tmp, 0);
		tmp = min(tmp, (mid - i + 1));
		long long val = IT.get(ver[mid], ver[i - 1], tmp);
		if (val >= opt) opt = val, pos = i;
	}
	res = max(res, opt);
	go(l, mid - 1, L, pos);
	go(mid + 1, r, pos, R);
}

void solve() {
	IT.num = 0, IT.build(0, 1, n);
	vector< pair<int, int> > vec;
	for (int i = 1; i <= n; ++i) vec.push_back({a[i], i});
	sort(vec.begin(), vec.end());
	int cur = 0;
	for (int i = 1; i <= n; ++i) {
		int tmp = lower_bound(vec.begin(), vec.end(), make_pair(a[i], i)) - vec.begin() + 1;
		ver[i] = ++IT.num;
		IT.upd(ver[i], ver[i - 1], 1, n, tmp, a[i]);
	}
	go(start, n, 1, start);
}

long long int findMaxAttraction(int _n, int _start, int _d, int attraction[]) {
	n = _n, d = _d, start = _start + 1;
	for (int i = 1; i <= n; ++i) a[i] = attraction[i - 1];
	solve();
	reverse(a + 1, a + n + 1);
	start = n + 1 - start;
	solve();
	return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve()':
holiday.cpp:99:6: warning: unused variable 'cur' [-Wunused-variable]
  int cur = 0;
      ^~~
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