2011 Dragon

二度とこんな問題は解きたくないです。

#include<stdio.h>
#include<algorithm>
using namespace std;
pair<int,int>dat[100000];
int tx[100000];
int ty[100000];
int x[100000];
int y[100000];
int n;
int p,q;
pair<int,int>N[100000];
pair<int,int>M[100000];
long long segtree[3][262144];
void set(int c,int a,long long b){
	a+=131072;
	segtree[c][a]=b;
	a/=2;
	while(a){
		segtree[c][a]=max(segtree[c][a*2],segtree[c][a*2+1]);
		a/=2;
	}
}
long long query(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return -1999999999;
	if(c<=a&&b<=d)return segtree[f][e];
	return max(query(a,(a+b)/2,c,d,e*2,f),query((a+b)/2+1,b,c,d,e*2+1,f));
}
long long solve(){
	for(int i=0;i<n;i++){
		tx[i]=dat[i].first;
		ty[i]=dat[i].second;
	}
	std::sort(tx,tx+n);
	std::sort(ty,ty+n);
	for(int i=0;i<262144;i++){
		segtree[0][i]=0;
		segtree[1][i]=segtree[2][i]=-1999999999;
	}
	int X=0;
	int Y=0;
	x[X++]=tx[0];
	y[Y++]=ty[0];
	for(int i=1;i<n;i++){
		if(tx[i]!=tx[i-1])x[X++]=tx[i];
		if(ty[i]!=ty[i-1])y[Y++]=ty[i];
	}
	for(int i=0;i<Y;i++){
		set(1,i,y[i]);
		set(2,i,q-y[i]+1);
	}
	for(int i=0;i<n;i++){
		N[i]=make_pair(lower_bound(x,x+X,dat[i].first)-x,lower_bound(y,y+Y,dat[i].second)-y);
		M[i]=dat[i];
	}
	std::sort(N,N+n);
	std::sort(M,M+n);
	long long ad=(long long)(p-X)*(q-Y);
	long long ret=0;
	for(int i=0;i<n;i++){
		if(lower_bound(x,x+X,M[i].first)-x){
			int S=x[lower_bound(x,x+X,M[i].first)-x-1];
			int L=lower_bound(y,y+Y,M[lower_bound(M,M+n,make_pair(S,-1))-M].second)-y;
			int R=lower_bound(y,y+Y,M[upper_bound(M,M+n,make_pair(S,1999999999))-1-M].second)-y;
			long long val=-1999999999;
			if(L>0){
				long long V=query(0,131071,0,L-1,1,1)-1;
				if(V>0){
					val=max(val,V-(upper_bound(y,y+Y,V)-y));
					//printf("[%lld] ",V-(upper_bound(y,y+Y,V)-y));
				}
			}//q-V-1=q-(q-y[i]+1)-1
			if(R<Y-1){
				long long V=query(0,131071,R+1,Y-1,1,2)-1;
				if(V>0){
					val=max(val,V-(Y-(upper_bound(y,y+Y,q-V)-y)));
				//	printf("(%lld)",V-(Y-(upper_bound(y,y+Y,q-V)-y)));
				}
			}
		//	printf("\n");
	//		printf("%lld %d\n",val,S-(lower_bound(x,x+X,S+1)-x));
			ret=max(ret,val+S-(upper_bound(x,x+X,S)-x));
		}
		ret=max(ret,(long long)segtree[0][N[i].second+131072]+M[i].first-2-(lower_bound(x,x+X,M[i].first-1)-x));
		set(0,N[i].second,-1999999999);
		set(1,N[i].second,-1999999999);
		set(2,N[i].second,-1999999999);
	}
//	printf("%lld %lld\n",ret,ad);
	return ret+ad;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	n=c;
	for(int i=0;i<c;i++)scanf("%d%d",&dat[i].first,&dat[i].second);
	long long ret=0;
	p=a;
	q=b;
	for(int j=0;j<4;j++){
		ret=max(ret,solve());
		for(int i=0;i<c;i++){
			dat[i]=make_pair(dat[i].second,p+1-dat[i].first);
		}
		swap(p,q);
	}
	printf("%lld\n",ret);
}