二度とこんな問題は解きたくないです。
#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); }