Submission #11918876

---

Source Code Expand

//Love and Freedom.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
#define ll long long
#define inf 20021225
#define N 300010
#define ls x<<1
#define rs x<<1|1
#define mid (l+r>>1)
#define pa pair<int,int>
#define fs first
#define se second
#define mp make_pair
using namespace std;
int read()
{
	int s=0,t=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')	t=-1; ch=getchar();}
	while(ch>='0' && ch<='9')	s=s*10+ch-'0',ch=getchar();
	return s*t;
}
int tag[N<<2],mx[N<<2];
void puttag(int x,int t){tag[x]+=t,mx[x]+=t;}
void pushdown(int x)
{
	if(!tag[x])	return;
	puttag(ls,tag[x]),puttag(rs,tag[x]),tag[x]=0;
}
void pushup(int x){mx[x]=max(mx[ls],mx[rs]);}
void modify(int x,int l,int r,int LL,int RR,int t)
{
	if(l>=LL&&r<=RR)	return void(puttag(x,t)); pushdown(x);
	if(LL<=mid)	modify(ls,l,mid,LL,RR,t);
	if(RR>mid)	modify(rs,mid+1,r,LL,RR,t);
	pushup(x);
}
int query(int x,int l,int r,int LL,int RR)
{
	if(LL<=l&&RR>=r)	return mx[x]; pushdown(x); int ans=0;
	if(LL<=mid)	ans=max(ans,query(ls,l,mid,LL,RR));
	if(RR>mid)	ans=max(ans,query(rs,mid+1,r,LL,RR));
	return ans;
}
struct poi{int x,y;}s[N];
bool operator<(poi a,poi b){return a.x==b.x?a.y<b.y:a.x<b.x;}
int n,w,h,ans; stack<pa> L,R;
void solve()
{
	sort(s+1,s+n+1); while(!L.empty()) L.pop(); while(!R.empty()) R.pop();
	memset(tag,0,sizeof(tag)),memset(mx,0,sizeof(mx));
	for(int i=1;i<=n;i++)
	{
		if(s[i].y<=h/2)
		{
			int nxt=i-1;
			while(!L.empty()&&L.top().se<=s[i].y)
				modify(1,1,n,L.top().fs,nxt,L.top().se-s[i].y),
				nxt=L.top().fs-1,L.pop();
			if(nxt!=i-1)	L.push(mp(nxt+1,s[i].y));
		}
		else
		{
			int nxt=i-1;
			while(!R.empty()&&R.top().se>=s[i].y)
				modify(1,1,n,R.top().fs,nxt,s[i].y-R.top().se),
				nxt=R.top().fs-1,R.pop();
			if(nxt!=i-1)	R.push(mp(nxt+1,s[i].y));
		}
		
		L.push(mp(i,0)); R.push(mp(i,h));
		modify(1,1,n,i,i,h-s[i].x);
		ans=max(ans,s[i+1].x+mx[1]);
	}
}
void init()
{
	w=read(),h=read(),n=read();
	for(int i=1;i<=n;i++)	s[i].x=read(),s[i].y=read();
	s[++n]=poi{0,0}; s[++n]=poi{w,h};
}
void work()
{
	solve();
	for(int i=1;i<=n;i++)	swap(s[i].x,s[i].y); swap(w,h);
	solve(); printf("%d\n",ans*2);
}
int main()
{
	init(); work();
	return 0;
}

Submission Info

Judge Result