Submission #1691848

---

Source Code Expand

#include<bits/stdc++.h>
const int N=3e5+7,inf=0x3f3f3f3f;
char ib[N*50],*ip=ib;
int _(){
	int x=0;
	while(*ip<48)++ip;
	while(*ip>47)x=x*10+*ip++-48;
	return x;
}
void maxs(int&a,int b){if(a<b)a=b;}
struct pos{
	int x,y;
	bool operator<(const pos&w)const{return x<w.x;}
}ps[N];
int ss1[N],ss2[N],sp1=0,sp2=0;
int xm,ym,m,n,ans=0,b1[N],b2[N],t1[1<<20|111],t2[1<<20|111],mx;
void ins(int*f,int x,int y){
	for(++x;x<N;x+=x&-x)maxs(f[x],y);
}
int gmx(int*f,int x){
	int v=-inf;
	for(++x;x;x-=x&-x)maxs(v,f[x]);
	return v;
}
void insx(int*f,int x,int y){
	for(x+=mx+1;x;x>>=1)maxs(f[x],y);
}
int gmx(int*f,int l,int r){
	int v=-inf;
	for(l+=mx,r+=mx+2;r-l>1;l>>=1,r>>=1){
		if(~l&1)maxs(v,f[l+1]);
		if(r&1)maxs(v,f[r-1]);
	}
	return v;
}
struct itv{
	int l,r,v;
	bool operator<(const itv&w)const{return r>w.r;}
	void cal(){
		int L=ps[l].x,R=ps[r].x;
		if(v<=m){
			maxs(ans,gmx(b1,l)-v+R-L);
			maxs(ans,gmx(t1,l,r)-v+R);
			ins(b2,l,-v);
			insx(t2,l,-v-L);
		}else{
			maxs(ans,gmx(b2,l)+v+R-L);
			maxs(ans,gmx(t2,l,r)+v+R);
			ins(b1,l,v);
			insx(t1,l,v-L);
		}
	}
}is[N];
#define clr(a) memset(a,-0x3f,sizeof(a))
#define push(ss,sp,op,y,lr,i) do{for(;sp&&ps[ss[sp]].y op y;is[ss[sp--]].lr=i);ss[++sp]=i;}while(0)
void cal2(){
	for(int i=1;i<=n;++i){
		int y=is[i].v=ps[i].y;
		push(ss1,sp1,>,y,r,i);
	}
	for(;sp1;is[ss1[sp1--]].r=n+1);
	for(int i=n;i>=1;--i){
		int y=ps[i].y;
		push(ss1,sp1,>=,y,l,i);
	}
	for(;sp1;is[ss1[sp1--]].l=0);
	for(int i=1;i<=n;++i)maxs(ans,ps[is[i].r].x-ps[is[i].l].x+is[i].v);
}
void cal(){
	m=ym/2;
	std::sort(ps+1,ps+n+1);
	ps[0].x=0,ps[n+1].x=xm;
	for(int i=0;i<=n;++i)maxs(ans,ps[i+1].x-ps[i].x+ym);
	for(int i=1;i<=n;++i){
		int y=is[i].v=ps[i].y;
		if(y<=m)push(ss1,sp1,<,y,r,i);
		else push(ss2,sp2,>,y,r,i);
	}
	for(;sp1;is[ss1[sp1--]].r=n+1);
	for(;sp2;is[ss2[sp2--]].r=n+1);
	for(int i=n;i>=1;--i){
		int y=ps[i].y;
		if(y<=m)push(ss1,sp1,<=,y,l,i);
		else push(ss2,sp2,>=,y,l,i);
	}
	for(;sp1;is[ss1[sp1--]].l=0);
	for(;sp2;is[ss2[sp2--]].l=0);
	std::sort(is+1,is+n+1);
	clr(b1),clr(b2),clr(t1),clr(t2);
	for(int i=1;i<=n;++i)is[i].cal();
	cal2();
	for(int i=1;i<=n;++i)ps[i].y=ym-ps[i].y;
	cal2();
}
int main(){
	fread(ib,1,sizeof(ib),stdin);
	xm=_(),ym=_(),n=_();
	for(mx=2;mx<n+5;mx<<=1);
	maxs(ans,xm+1);
	maxs(ans,ym+1);
	for(int i=1;i<=n;++i){
		ps[i].x=_();
		ps[i].y=_();
	}
	cal();
	std::swap(xm,ym);
	for(int i=1;i<=n;++i)std::swap(ps[i].x,ps[i].y);
	cal();
	printf("%d\n",ans*2);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:96:30: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
  fread(ib,1,sizeof(ib),stdin);
                              ^

Judge Result