Submission #245341

#	Time	Username	Problem	Language	Result	Execution time	Memory
245341		vioalbert	Holiday (IOI14_holiday)	C++14	100 / 100	1559 ms	15852 KiB

holiday

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

const int N = 1e5+5;
int n, start, d;
ll attraction[N], dp[N];
map<ll, int> cidx;
vector<ll> cval;

int walk(int l, int r) {
	return r-l + min(start-l, r-start);
}

struct SegmentTree {
	int n, l, r;
	vector<ll> sum, cnt;
	SegmentTree(int _n) : n(_n), l(0), r(-1) {
		sum.assign(4*n, 0);
		cnt.assign(4*n, 0);
	}
	void update(int idx, int l, int r, int x, ll val) {
		if(r < x || x < l) return;
		else if(l == r) {
			sum[idx] += cval[l] * val;
			cnt[idx] += val;
			return;
		}
		int lc = idx<<1, rc = lc|1;
		update(lc, l, (l+r)/2, x, val);
		update(rc, (l+r)/2+1, r, x, val);
		sum[idx] = sum[lc] + sum[rc];
		cnt[idx] = cnt[lc] + cnt[rc];
	}
	ll queryKth(int idx, int l, int r, int k) {
		if(k <= 0 || l > r) return 0;
		if(cnt[idx] <= k) return sum[idx];
		if(l == r) return k * cval[l];
		int mid = (l+r)/2, lc = idx<<1, rc = lc|1;
		if(k <= cnt[rc])
			return queryKth(rc, mid+1, r, k);
		else
			return queryKth(rc, mid+1, r, cnt[rc]) + queryKth(lc, l, mid, k-cnt[rc]);
	}
};
SegmentTree *st;

ll cost(int l, int r, int k) {
	if(k <= 0) return 0;
	while(st->r < r) st->update(1, 0, n-1, cidx[attraction[++st->r]], 1);
	while(st->r > r) st->update(1, 0, n-1, cidx[attraction[st->r--]], -1);
	while(st->l > l) st->update(1, 0, n-1, cidx[attraction[--st->l]], 1);
	while(st->l < l) st->update(1, 0, n-1, cidx[attraction[st->l++]], -1);
	return st->queryKth(1, 0, n-1, k);
}

void solve(int l, int r, int optL, int optR) {
	if(l > r) return;
	int mid = (l+r)>>1, best = -1;
	ll& ret = dp[mid] = -1e15;
	for(int i = optL; i <= optR; i++) {
		ll cur = cost(mid, i, d - walk(mid, i));
		if(ret < cur)
			ret = cur, best = i;
	}
	solve(l, mid-1, optL, best);
	solve(mid+1, r, best, optR);
}

ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
	n = _n, start = _start, d = _d;
	for(int i = 0; i < n; i++)
		attraction[i] = _attraction[i];

	for(int i = 0; i < n; i++)
		cval.push_back(attraction[i]);
	sort(cval.begin(), cval.end());
	auto it = unique(cval.begin(), cval.end());
	cval.erase(it, cval.end());
	for(int i = 0; i < cval.size(); i++)
		cidx[cval[i]] = i;

	st = new SegmentTree(n);
	solve(0, start, start, n-1);
	ll ans = 0;
	for(int i = 0; i <= start; i++)
		ans = max(ans, dp[i]);
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cval.size(); i++)
                 ~~^~~~~~~~~~~~~

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