제출 #1318909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318909		boclobanchat	휴가 (IOI14_holiday)	C++20	23 / 100	39 ms	4660 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
long long fen[MAXN][2],A[MAXN],pos[MAXN],P[MAXN];
int l=1,r=0,N;
bool comp(int a,int b) { return A[a]>A[b]; }
int getlog(long long n) { return 63-__builtin_clzll(n); }
void update(int i,int c,int n,long long val) { for(;i<=n;i+=i&-i) fen[i][c]+=val; }
long long get(int i,int c) { long long ans=0;for(;i;i-=i&-i) ans+=fen[i][c];return ans; }
long long walk(int n,long long val)
{
	long long pos=0,ans=0;
	for(int i=getlog(n);i+1;i--) if(pos+(1<<i)<=n&&val>=fen[pos+(1<<i)][0])
		pos+=(1<<i),val-=fen[pos][0],ans+=fen[pos][1];
	return ans;
}
void updnode(int idx,int val)
{
	if(val>0) update(idx,0,N,1);
	else update(idx,0,N,-1);
	update(idx,1,N,val);
}
long long solve(int pl,int pr,int cnt)
{
	while(r<pr) r++,updnode(P[r],A[r]);
	while(r>pr) updnode(P[r],-A[r]),r--;
	while(l<pl) updnode(P[l],-A[l]),l++;
	while(l>pl) l--,updnode(P[l],A[l]);
	return walk(N,cnt-pr+pl);
}
long long findMaxAttraction(int n,int start,int d,int attraction[])
{
	N=n,start++;
	for(int i=0;i<n;i++) A[i+1]=attraction[i],pos[i+1]=i+1;
	sort(pos+1,pos+n+1,comp);
	for(int i=1;i<=n;i++) P[pos[i]]=i;
	long long ans=0,mxa=-1,res;
	int op=0;
	for(int i=start;i;i--) if(mxa<(res=solve(i,start,d))) mxa=res,op=i;
	ans=max(ans,mxa);
	for(int i=start+1;i<=n;i++)
	{
		int l=max(1,op-1),r=min(n,op+1);
		mxa=-1;
		for(int j=l;j<=r&&j<=i;j++) if(mxa<(res=solve(j,i,d-i+start))) mxa=res,op=j;
		ans=max(ans,mxa);
	}
	mxa=-1;
	for(int i=start;i<=n;i++) if(mxa<(res=solve(start,i,d))) mxa=res,op=i;
	ans=max(ans,mxa);
	for(int i=start-1;i;i--)
	{
		int l=max(1,op-1),r=min(n,op+1);
		mxa=-1;
		for(int j=max(l,i);j<=r;j++) if(mxa<(res=solve(j,i,d-start+i))) mxa=res,op=j;
		ans=max(ans,mxa);
	}
	return ans;
}

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