Submission #852374

#	Time	Username	Problem	Language	Result	Execution time	Memory
852374		adaawf	Holiday (IOI14_holiday)	C++14	100 / 100	266 ms	15300 KiB

holiday

#include <iostream>
#include <vector>
#include <algorithm>
#include "holiday.h"
using namespace std;
pair<int, int> a[400005];
long long f[400005], g[400005], res = 0;
int d;
struct DAY {
	long long int res, c;
};
DAY t[1600005];
void update(int v, int x) {
 	v += 400005;
	if (x < 0) t[v].c = 0;
	else t[v].c = 1;
	t[v].res += x;
	v /= 2;
	while (v > 0) {
		t[v].c = t[v * 2].c + t[v * 2 + 1].c;
		t[v].res = t[v * 2].res + t[v * 2 + 1].res;
		v /= 2;
	}
}
long long int sum(int v, int l, int r, int x) {
	if (t[v].c == 0 || x <= 0) return 0;
	if (t[v].c <= x) return t[v].res;
    int mid = (l + r) / 2;
    if (t[v * 2 + 1].c >= x) return sum(v * 2 + 1, mid + 1, r, x);
    return t[v * 2 + 1].res + sum(v * 2, l, mid, x - t[v * 2 + 1].c);
}
int ll = 0, rr = -1;
void trya(int x, int y) {
	while (ll > x) {
		ll--;
		update(a[ll].second, a[ll].first);
	}
	while (rr < y) {
		rr++;
		update(a[rr].second, a[rr].first);
	}
	while (ll < x) {
		update(a[ll].second, -a[ll].first);
		ll++;
	}
	while (rr > y) {
		update(a[rr].second, -a[rr].first);
		rr--;
	}
}
void dnc(int l, int r, int x, int y, int k) {
    if (l > r) return;
	int mid = (l + r) / 2;
	trya(x, mid);
	int h = x;
	for (int i = x; i <= min(mid, y) && i <= k; i++) {
		int c = (k - i) + (mid - i);
		if (d - c > 0) {
			long long int k = sum(1, 0, 400004, d - c);
			if (f[mid] <= k) {
				f[mid] = k;
				res = max(res, k);
				h = i;
			}
		}
		update(a[i].second, -a[i].first);
		ll++;
	}
	dnc(l, mid - 1, x, h, k);
	dnc(mid + 1, r, h, y, k);
}
void dnc2(int l, int r, int x, int y, int k) {
    if (l > r) return;
	int mid = (l + r) / 2;
	trya(mid, y);
	int h = y;
	for (int i = y; i >= max(mid, x) && i >= k; i--) {
		int c = (i - k) + (i - mid);
		if (d - c > 0) {
			long long int k = sum(1, 0, 400004, d - c);
			if (g[mid] <= k) {
				g[mid] = k;
				res = max(res, k);
				h = i;
			}
		}
		update(a[i].second, -a[i].first);
		rr--;
	}
	dnc2(l, mid - 1, x, h, k);
	dnc2(mid + 1, r, h, y, k);
}
long long int findMaxAttraction(int n, int k, int dd, int attraction[]) {
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		v.push_back({attraction[i], i});
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		a[v[i].second] = {v[i].first, i};
	}
	d = dd;
	dnc(k, n - 1, 0, n - 1, k);
	dnc2(0, k, 0, n - 1, k);
    return res;
}

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