Submission #221951

#	Time	Username	Problem	Language	Result	Execution time	Memory
221951		DystoriaX	Holiday (IOI14_holiday)	C++14	23 / 100	895 ms	15328 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, sum = 0;
long long dp[300010], opt[300010], dps[300010], opts[300010], idx[300010];
vector<pair<int, int> > v;

priority_queue<int, vector<int>, greater<int> > pq;

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){
	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;

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

	dp[m] = 0, opt[m] = -1;

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

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

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

		if(dp[m] < x){
			dp[m] = x;
			opt[m] = i;
		}
	}

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

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

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

	dps[m] = 0, opts[m] = -1;

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

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

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

		if(dps[m] < x){
			dps[m] = x;
			opts[m] = i;
		}
	}

	solveS(l, m - 1, opts[m], optR, pvt);
	solveS(m + 1, r, optL, opts[m], 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;
	solveS(0, d, 0, start - 1, start - 1);

	for(int i = 0; i <= d; i++){
		// cerr << i << " -> " << dps[i] << " " << opts[i] << endl;
		// cerr << d - i - (opt[i] - start) - 1 << endl;

		ans = max(ans, max(dp[i], dps[i]));

		//Go right, then left
		if(opt[i] != -1 && d - i - (opt[i] - start) - 1 > 0) ans = max(ans, dp[i] + dps[d - i - (opt[i] - start) - 1]);

		//Go left, then right
		if(opts[i] != -1 && d - i - (start - 1 - opts[i]) - 1 > 0) ans = max(ans, dps[i] + dp[d - i - (start - 1 - opts[i]) - 1]);
	}

    return ans;
}

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