Submission #222220

#	Time	Username	Problem	Language	Result	Execution time	Memory
222220		DystoriaX	Holiday (IOI14_holiday)	C++14	100 / 100	916 ms	13032 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

struct Node{
	long long val = 0;
	int active = 0;
};

int n;
Node st[400010];
long long int ans;
int idx[300010];
vector<pair<int, int> > v;

long long f[300010], g[300010];
int optF[300010], optG[300010];

void update(int l, int r, int pt, bool val, int i){
	if(pt < l || r < pt) return;

	if(l == r && l == pt){
		st[i].active = val;

		if(st[i].active) st[i].val = v[l].first;
		else st[i].val = 0;

		return;
	}

	int m = (l + r) >> 1;

	update(l, m, pt, val, i << 1);
	update(m + 1, r, pt, val, 1 + (i << 1));

	st[i].val = st[i << 1].val + st[1 + (i << 1)].val;
	st[i].active = st[i << 1].active + st[1 + (i << 1)].active;
}

long long query(int l, int r, int val, int i){
	if(val == 0) return 0;
	if(st[i].active <= val) return st[i].val;

	int m = (l + r) >> 1;

	return query(l, m, min(val, st[i << 1].active), i << 1) + query(m + 1, r, max(0, val - st[i << 1].active), 1 + (i << 1));
}

void update(int pt, bool val){
	update(0, n - 1, pt, val, 1);
}

long long query(int val){
	if(val <= 0) return 0;
	return query(0, n - 1, val, 1);
}

int now;

void solve(int l, int r, int optL, int optR, int pvt){
	if(l > r) return;

	long long val = -1;
	int opt = -1;

	int m = (l + r) >> 1;

	while(now < optL) update(idx[++now], 1);
	while(now > optL) update(idx[now--], 0);

	for(int i = optL; i <= optR; i++){
		if(now < i) update(idx[++now], 1);

		long long x = query(m - (i - pvt));

		if(x > val){
			val = x;
			opt = i;
		}
	}

	f[m] = val;
	optF[m] = opt;

	solve(l, m - 1, optL, opt, pvt);
	solve(m + 1, r, opt, optR, pvt);
}

void solveS(int l, int r, int optL, int optR, int pvt){
	if(l > r) return;

	long long val = -1;
	int opt = -1;

	int m = (l + r) >> 1;

	while(now > optR) update(idx[--now], 1);
	while(now < optR) update(idx[now++], 0);

	for(int i = optR; i >= optL; i--){
		if(now > i) update(idx[--now], 1);

		long long x = query(m - (pvt - i));

		if(x > val){
			val = x;
			opt = i;
		}
	}

	g[m] = val;
	optG[m] = opt;

	solveS(l, m - 1, opt, optR, pvt);
	solveS(m + 1, r, optL, opt, pvt);
}

long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
	n = N;
	for(int i = 0; i < n; i++) v.emplace_back(attraction[i], i);

	sort(v.rbegin(), v.rend());

	for(int i = 0; i < n; i++){
		idx[v[i].second] = i;
	}

	now = start - 1;
	solve(0, d, start, n - 1, start);

	while(now >= start) update(idx[now--], 0);
	now = start;

	if(start > 0) solveS(0, d, 0, start - 1, start - 1);

	for(int i = 1; i <= d; i++){
		// cout << i << " -> " << g[i] << " " << optG[i] << endl;
		ans = max(ans, max(f[i], g[i - 1]));

		if(d - i - (optF[i] - start) - 1 > 0) ans = max(ans, f[i] + g[d - i - (optF[i] - start) - 1]);
		if(d - (i + 1) - (start - 1 - optG[i]) - 1 > 0) ans = max(ans, g[i] + f[d - i - (start - optG[i]) - 1]);
	}

    return ans;
}

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