Submission #1372381

---

Source Code Expand

#include<bits/stdc++.h>
#define sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define inf 0x3f3f3f3f
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout);
using namespace std;
 
const int N=1050005,M=100005,mod=1e9+7;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
inline void ch(int &x,int y){x=(x+y)%mod;}
inline void read(int &x){
	x=0;char ch=getchar(),rev=0;
	while(ch>'9'||ch<'0') rev=(ch=='-'),ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	x=rev?-x:x;
}
inline int exp(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}
int w,h,n,cnt,ans,x[N],y[N],yy[N],sta[N][2],g[N][2],top[2];
int p[N<<2],flag[N<<2];
 
inline void ins(int x){if(x>=1&&x<h) yy[++cnt]=x;}
inline int get(int y){return lower_bound(yy+1,yy+cnt+1,y)-yy;}
inline void add(int k,int b){p[k]+=b;flag[k]+=b;}
inline void push(int k){
	if(!flag[k]) return;
	add(ls,flag[k]);add(rs,flag[k]);
	flag[k]=0;
}
void ch(int l,int r,int x,int y,int k,int b){
	if(x<=l&&r<=y){add(k,b);return;}
	push(k);
	int mid=l+r>>1;
	if(x<=mid) ch(l,mid,x,y,ls,b);
	if(y>mid) ch(mid+1,r,x,y,rs,b);
	p[k]=max(p[ls],p[rs]);
}
void build(int l,int r,int k){
	if(l==r){p[k]=-yy[l];return;}
	int mid=l+r>>1;
	build(l,mid,ls);build(mid+1,r,rs);
	p[k]=max(p[ls],p[rs]);
}
void solve(int mid){
	clr(flag,0);clr(top,0);cnt=0;
	ins(1);ins(h-1);
	for(int i=1;i<=n;i++){
		ins(y[i]);
		ins(y[i]-1);
		ins(y[i]+1);
	}
	sort(yy+1,yy+cnt+1);
	cnt=unique(yy+1,yy+cnt+1)-yy-1;
	build(1,cnt,1);
	for(int i=1;i<=cnt;i++)
		g[i][0]=mid,g[i][1]=w-mid;
	for(int i=1;i<=n;i++)
		if(x[i]<=mid) gmin(g[get(y[i])][0],mid-x[i]); else gmin(g[get(y[i])][1],x[i]-mid);
	for(int i=1;i<=cnt;i++){
		for(int x=0;x<2;x++){
			int last=i;
			ch(1,cnt,i,i,1,g[i][x]);
			while(top[x]&&g[sta[top[x]][x]][x]>g[i][x]){
				int l=sta[top[x]-1][x]+1,r=sta[top[x]][x];
				ch(1,cnt,l,r,1,g[i][x]-g[r][x]);
				top[x]--;
			}
			sta[++top[x]][x]=i;
		}
		gmax(ans,(p[1]+yy[i]+2)*2);
	}
}
 
int main(){
#ifdef rqgao2014
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d%d",&w,&h,&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x[i],&y[i]);
	solve(w/2);
	for(int i=1;i<=n;i++)
		swap(x[i],y[i]);
	swap(w,h);solve(w/2);
	printf("%d\n",max(ans,max(w,h)*2+2));
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:99:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&w,&h,&n);
                          ^
./Main.cpp:101:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x[i],&y[i]);
                            ^

Judge Result