Submission #242658

#	Time	Username	Problem	Language	Result	Execution time	Memory
242658		maximath_1	Holiday (IOI14_holiday)	C++11	100 / 100	878 ms	6904 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=4e18;
ll ans=0ll;
pair<int, int>a[100005];
int n, s, d, ptr, pos[100005];
pair<ll, int>st[100005*4];
void upd(int nd, int cl, int cr, int pos, bool is){
	if(cl == cr){
		if(is) st[nd] = {a[pos].first, 1};
		else st[nd] = {0, 0};
		return;
	}
	int md = (cl+cr)/2;
	if(pos<=md) upd(nd*2, cl, md, pos, is);
	else upd(nd*2+1, md+1, cr, pos, is);
	st[nd] = {st[nd*2].first+st[nd*2+1].first, st[nd*2].second+st[nd*2+1].second};
}
ll k_best(int nd, int cl, int cr, int k){
	if(k <= 0) return 0;
	if(st[nd].second <= k) return st[nd].first;
	int md = (cl+cr)/2;
	if(st[nd*2].second >= k)
		return k_best(nd*2, cl, md, k);
	return st[nd*2].first + k_best(nd*2+1, md+1, cr, k-st[nd*2].second);
}
void solve(int l, int r, int opt_l, int opt_r){
	if(l > r) return;
	int md = (l+r)/2;
	pair<ll, int> res = {-inf, -1};
	if(md < ptr)
		for(int i=md; i<ptr; i++)
			upd(1, 1, n, pos[i], true);
	else
		for(int i=ptr; i<md; i++)
			upd(1, 1, n, pos[i], false);
	ptr = md;
	for(int i=opt_l; i<=opt_r; i++){
		upd(1, 1, n, pos[i], true);
		res = max(res, {k_best(1, 1, n, d+2*md-s-i), -i});
	}
	ans = max(ans, res.first);
	int opt = -res.second;
	for(int i=opt; i<=opt_r; i++)
		upd(1, 1, n, pos[i], false);
	solve(md+1, r, opt, opt_r);
	for(int i=opt_l; i<opt; i++)
		upd(1, 1, n, pos[i], false);
	solve(l, md-1, opt_l, opt);
}
ll findMaxAttraction(int N, int S, int D, int A[]){
	n = N, s = S+1, d = D;
	for(int i=1; i<=n; i++)
		a[i] = {A[i-1], i};
	sort(a+1, a+n+1, greater<pair<int, int> >());
	for(int i=1; i<=n; i++)
		pos[a[i].second] = i;
	ptr = s+1;
	solve(1, s, s, n);
	for(int i=1; i<=n; i++){
		pos[n-a[i].second+1] = i;
		upd(1, 1, n, i, false);
	}
	s = n-s+1;
	ptr = s+1;
	solve(1, s, s, n);
	return ans;
}

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