제출 #228501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228501		kig9981	휴가 (IOI14_holiday)	C++17	7 / 100	205 ms	54648 KiB

holiday

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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct PST
{
	int l, r, c;
	long long s;
	PST() : l(0), r(0), c(0), s(0) {}
};

const int SZ=1<<17;
PST tree[2222222];
int node_cnt, N, s, d, xsz, A[100000], x[100000];
long long ans;

void add_tree(int b, int n, int v, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(s==e) {
		tree[p].s=tree[b].s+v;
		tree[p].c=tree[b].c+1;
		return;
	}
	if(n<=m) {
		tree[node_cnt]=PST();
		tree[p].l=node_cnt++;
		tree[p].r=tree[b].r;
		add_tree(tree[b].l,n,v,tree[p].l,s,m);
	}
	else {
		tree[node_cnt]=PST();
		tree[p].r=node_cnt++;
		tree[p].l=tree[b].l;
		add_tree(tree[b].r,n,v,tree[p].r,m+1,e);
	}
	tree[p].s=tree[tree[p].l].s+tree[tree[p].r].s;
	tree[p].c=tree[tree[p].l].c+tree[tree[p].r].c;
}

int kth(int l, int r, int k)
{
	int s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(tree[tree[r].l].c-tree[tree[l].l].c>=k) {
			l=tree[l].l;
			r=tree[r].l;
			e=m;
		}
		else {
			k-=tree[tree[r].l].c-tree[tree[l].l].c;
			l=tree[l].r;
			r=tree[r].r;
			s=m+1;
		}
	}
	return s;
}

long long get_sum(int n1, int n2, int p, int s=0, int e=SZ-1)
{
	int m=(s+e)>>1;
	if(p==0 || n2<n1 || n2<s || e<n1) return 0;
	if(n1<=s && e<=n2) return tree[p].s;
	return get_sum(n1,n2,tree[p].l,s,m)+get_sum(n1,n2,tree[p].r,m+1,e);
}

void solve(int s1, int e1, int s2, int e2)
{
	int m1=(s1+e1)>>1, m2=-1, k;
	long long mx=-1, t;
	if(s1>e1) return;
	for(int i=s2;i<=e2;i++) if(d>2*(s-m1)+i-s) {
		k=kth(m1,i+1,min(d-2*(s-m1)-i+s,i-m1+1));
		if((t=get_sum(0,k,i+1)-get_sum(0,k,m1))>mx) {
			mx=t;
			m2=i;
		}
	}
	if(mx==-1) {
		solve(m1+1,e1,s2,e2);
		return;
	}
	ans=max(ans,mx);
	solve(s1,m1-1,s2,m2);
	solve(m1+1,e1,m2,e2);
}

long long findMaxAttraction(int n, int start, int d, int attraction[])
{
	N=n; s=start; ::d=d;
	if(d==0) return 0;
	for(int i=0;i<N;i++) x[i]=A[i]=attraction[i];
	sort(x,x+N);
	xsz=unique(x,x+N)-x;
	node_cnt=N+1;
	for(int i=0;i<N;i++) {
		A[i]=lower_bound(x,x+xsz,A[i])-x;
		add_tree(i,xsz-1-A[i],x[A[i]],i+1);
	}
	solve(max(0,s-d+1),s,s,min(s+d-1,N-1));
	reverse(A,A+N); s=N-1-s;
	node_cnt=N+1;
	for(int i=0;i<N;i++) {
		tree[i+1]=PST();
		add_tree(i,xsz-1-A[i],x[A[i]],i+1);
	}
	solve(max(0,s-d+1),s,s,min(s+d-1,N-1));
	return ans;
}

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