Submission #704639

#	Time	Username	Problem	Language	Result	Execution time	Memory
704639		vjudge1	Holiday (IOI14_holiday)	C++14	Compilation error	0 ms	0 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;
	}
}
int main(){
	scanf("%d%d%d",&n,&s,&d); ++s;
	for(i=1;i<=n;++i) scanf("%d",a+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)); printf("%lld",ans);
	return 0;
}

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;
      |                           ^~~
holiday.cpp: In function 'int main()':
holiday.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d",&n,&s,&d); ++s;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
holiday.cpp:49:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  for(i=1;i<=n;++i) scanf("%d",a+i),build();
      |                    ~~~~~^~~~~~~~~~
/usr/bin/ld: /tmp/cc3DeKaY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccO3P1LY.o:holiday.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc3DeKaY.o: in function `main':
grader.cpp:(.text.startup+0xaf): undefined reference to `findMaxAttraction(int, int, int, int*)'
collect2: error: ld returned 1 exit status