제출 #704644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704644		vjudge1	Holiday (IOI14_holiday)	C++14	0 / 100	80 ms	61676 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.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[]){
	for(i=n;i;--i) a[i]=a[i-1]; ++s; 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;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'void solve(int, int, int, int)':
holiday.cpp:11:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   11 |  if(ll>lr||rl>rr) return; int lm=(ll+lr)>>1;
      |  ^~
holiday.cpp:11:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   11 |  if(ll>lr||rl>rr) return; int lm=(ll+lr)>>1;
      |                           ^~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:49:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |  for(i=n;i;--i) a[i]=a[i-1]; ++s; for(i=1;i<=n;++i) build();
      |  ^~~
holiday.cpp:49:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   49 |  for(i=n;i;--i) a[i]=a[i-1]; ++s; for(i=1;i<=n;++i) build();
      |                              ^~

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