Submission #704642

#	Time	Username	Problem	Language	Result	Execution time	Memory
704642		vjudge1	Holiday (IOI14_holiday)	C++14	0 / 100	75 ms	61744 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn=100010;
const int maxm=3200010;
int n,s,d,i,l,r,m,x,p1,p2,tot;
int a[maxn],rt[maxn]; LL ans,sum[maxm]; 
int ls[maxm],rs[maxm],cnt[maxm];
void solve(int ll,int lr,int rl,int rr){
	if(ll>lr||rl>rr) return; int lm=(ll+lr)>>1;
	if(d<(s-lm)<<1){solve(lm+1,lr,rl,rr);return;} 
	int rk=min(rr,rl+d-((s-lm)<<1)),rm=rl; LL mx=0,nw;
	for(i=rl;i<=rk;++i){
		l=0; r=1e9; x=d-(i-lm)-(s-lm); 
		nw=0; p1=rt[i]; p2=rt[lm-1];
		if(cnt[p1]-cnt[p2]<=x) nw=sum[p1]-sum[p2];
		else{
			while(l<r){
				m=(l+r)>>1;
				if(cnt[rs[p1]]-cnt[rs[p2]]<=x){
					x-=cnt[rs[p1]]-cnt[rs[p2]];
					nw+=sum[rs[p1]]-sum[rs[p2]];
					r=m; p1=ls[p1]; p2=ls[p2];
				}
				else l=m+1,p1=rs[p1],p2=rs[p2];
			}
			nw+=1LL*l*min(x,cnt[p1]-cnt[p2]);
		}
		if(nw>mx) mx=nw,rm=i;
	}
	if(ans<mx) ans=mx; 
	solve(ll,lm-1,rl,rm); 
	solve(lm+1,lr,rm,rr);
}
void build(){
	l=0; r=1e9; x=a[i]; rt[i]=++tot; p1=rt[i-1];
	ls[tot]=ls[p1]; rs[tot]=rs[p1];
	sum[tot]=sum[p1]+x; cnt[tot]=cnt[p1]+1;
	while(l<r){
		m=(l+r)>>1;
		if(x<=m) p1=ls[tot],ls[tot]=tot+1,r=m; 
		else p1=rs[tot],rs[tot]=tot+1,l=m+1;
		rs[++tot]=rs[p1]; ls[tot]=ls[p1];
		sum[tot]=sum[p1]+x; cnt[tot]=cnt[p1]+1;
	}
}
long long findMaxAttraction(int n,int s,int d,int a[]){
	++s; for(i=n;i;--i) a[i]=a[i-1]; for(i=1;i<=n;++i) build(); 
	solve(max(1,s-(d<<1)),s,s,min(n,s+d)); reverse(a+1,a+n+1); 
	s=n-s+1; tot=0; for(i=1;i<=n;++i) build();
	solve(max(1,s-(d<<1)),s,s,min(n,s+d)); return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:10:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   10 |  if(ll>lr||rl>rr) return; int lm=(ll+lr)>>1;
      |  ^~
holiday.cpp:10:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   10 |  if(ll>lr||rl>rr) return; int lm=(ll+lr)>>1;
      |                           ^~~

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