제출 #1228789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228789		PlayVoltz	휴가 (IOI14_holiday)	C++20	100 / 100	1885 ms	43856 KiB

holiday

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

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int start, L=0, R=-1, n;
vector<pii> vect;
vector<vector<int> > ll, rr;

struct node{
	int s, e, m, val, c;
	node *l, *r;
	node(int S, int E){
		s=S, e=E, m=(s+e)/2, val=0, c=0;
		if (s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void up(int i, int v){
		if (s==e)val+=v, c=!c;
		else{
			if (i<=m)l->up(i, v);
			else r->up(i, v);
			val=l->val+r->val;
			c=l->c+r->c;
		}
	}
	int bsta(int k){
		if (s==e)return s;
		if (r->c>=k)return r->bsta(k);
		return l->bsta(k-r->c);
	}
	int query(int left, int right){
		if (s==left && e==right)return val;
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return l->query(left, m)+r->query(m+1, right);
	}
}*st;

int cost(int l, int r, int d){
	if (d<0)return LLONG_MIN/2;
	if (!d)return 0;
	while(R<r)++R, st->up(vect[R].se, vect[R].fi);
	while(l<L)--L, st->up(vect[L].se, vect[L].fi);
	while(r<R)st->up(vect[R].se, -vect[R].fi), --R;
	while (L<l)st->up(vect[L].se, -vect[L].fi), ++L;
	return st->query(st->bsta(d), n-1);
}

void dncl(int l, int r, int optl, int optr, bool t){
	if (l>r)return;
	int mid=(l+r)/2, best=LLONG_MIN/2, opt;
	for (int i=optr; i>=optl; --i){
		int res=cost(i, start-1, mid-(start-i)*(1+t));
		if (res>best)best=res, opt=i;
	}
	ll[mid][t]=best;
	dncl(l, mid-1, opt, optr, t);
	dncl(mid+1, r, optl, opt, t);
}

void dncr(int l, int r, int optl, int optr, bool t){
	if (l>r)return;
	int mid=(l+r)/2, best=LLONG_MIN/2, opt;
	for (int i=optl; i<=optr; ++i){
		int res=cost(start+1, i, mid-(i-start)*(1+t));
		if (res>best)best=res, opt=i;
	}
	rr[mid][t]=best;
	dncr(l, mid-1, optl, opt, t);
	dncr(mid+1, r, opt, optr, t);
}

int findMaxAttraction(signed N, signed Start, signed d, signed attraction[]){
	n=N;
	start=Start;
	vect.resize(n);
	ll.resize(d+1, vector<int>(2, 0));
	rr.resize(d+1, vector<int>(2, 0));
	st = new node(0, n-1);
	vector<pii> temp(n);
	for (int i=0; i<n; ++i)temp[i]=mp(attraction[i], i);
	sort(temp.begin(), temp.end());
	for (int i=0; i<n; ++i)vect[temp[i].se]=mp(temp[i].fi, i);
	if (start)dncl(1, d, 0, start-1, 0);
	if (start)dncl(1, d, 0, start-1, 1);
	if (start!=n-1)dncr(1, d, start+1, n-1, 0);
	if (start!=n-1)dncr(1, d, start+1, n-1, 1);
	int ans=0;
	for (int i=0; i<=d; ++i){
		ans=max({ans, ll[i][0]+rr[d-i][1], ll[i][1]+rr[d-i][0]});
		if (i!=d)ans=max({ans, ll[i][0]+rr[d-i-1][1]+vect[start].fi, ll[i][1]+rr[d-i-1][0]+vect[start].fi});
	}
	return ans;
}

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