fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4. pair<int,int>dat[100000];
  5. int tx[100000];
  6. int ty[100000];
  7. int x[100000];
  8. int y[100000];
  9. int n;
  10. int p,q;
  11. pair<int,int>N[100000];
  12. pair<int,int>M[100000];
  13. long long segtree[3][262144];
  14. void set(int c,int a,long long b){
  15. 	a+=131072;
  16. 	segtree[c][a]=b;
  17. 	a/=2;
  18. 	while(a){
  19. 		segtree[c][a]=max(segtree[c][a*2],segtree[c][a*2+1]);
  20. 		a/=2;
  21. 	}
  22. }
  23. long long query(int a,int b,int c,int d,int e,int f){
  24. 	if(d<a||b<c)return -1999999999;
  25. 	if(c<=a&&b<=d)return segtree[f][e];
  26. 	return max(query(a,(a+b)/2,c,d,e*2,f),query((a+b)/2+1,b,c,d,e*2+1,f));
  27. }
  28. long long solve(){
  29. 	for(int i=0;i<n;i++){
  30. 		tx[i]=dat[i].first;
  31. 		ty[i]=dat[i].second;
  32. 	}
  33. 	std::sort(tx,tx+n);
  34. 	std::sort(ty,ty+n);
  35. 	for(int i=0;i<262144;i++){
  36. 		segtree[0][i]=0;
  37. 		segtree[1][i]=segtree[2][i]=-1999999999;
  38. 	}
  39. 	int X=0;
  40. 	int Y=0;
  41. 	x[X++]=tx[0];
  42. 	y[Y++]=ty[0];
  43. 	for(int i=1;i<n;i++){
  44. 		if(tx[i]!=tx[i-1])x[X++]=tx[i];
  45. 		if(ty[i]!=ty[i-1])y[Y++]=ty[i];
  46. 	}
  47. 	for(int i=0;i<Y;i++){
  48. 		set(1,i,y[i]);
  49. 		set(2,i,q-y[i]+1);
  50. 	}
  51. 	for(int i=0;i<n;i++){
  52. 		N[i]=make_pair(lower_bound(x,x+X,dat[i].first)-x,lower_bound(y,y+Y,dat[i].second)-y);
  53. 		M[i]=dat[i];
  54. 	}
  55. 	std::sort(N,N+n);
  56. 	std::sort(M,M+n);
  57. 	long long ad=(long long)(p-X)*(q-Y);
  58. 	long long ret=0;
  59. 	for(int i=0;i<n;i++){
  60. 		if(lower_bound(x,x+X,M[i].first)-x){
  61. 			int S=x[lower_bound(x,x+X,M[i].first)-x-1];
  62. 			int L=lower_bound(y,y+Y,M[lower_bound(M,M+n,make_pair(S,-1))-M].second)-y;
  63. 			int R=lower_bound(y,y+Y,M[upper_bound(M,M+n,make_pair(S,1999999999))-1-M].second)-y;
  64. 			long long val=-1999999999;
  65. 			if(L>0){
  66. 				long long V=query(0,131071,0,L-1,1,1)-1;
  67. 				if(V>0){
  68. 					val=max(val,V-(upper_bound(y,y+Y,V)-y));
  69. 					//printf("[%lld] ",V-(upper_bound(y,y+Y,V)-y));
  70. 				}
  71. 			}//q-V-1=q-(q-y[i]+1)-1
  72. 			if(R<Y-1){
  73. 				long long V=query(0,131071,R+1,Y-1,1,2)-1;
  74. 				if(V>0){
  75. 					val=max(val,V-(Y-(upper_bound(y,y+Y,q-V)-y)));
  76. 				//	printf("(%lld)",V-(Y-(upper_bound(y,y+Y,q-V)-y)));
  77. 				}
  78. 			}
  79. 		//	printf("\n");
  80. 	//		printf("%lld %d\n",val,S-(lower_bound(x,x+X,S+1)-x));
  81. 			ret=max(ret,val+S-(upper_bound(x,x+X,S)-x));
  82. 		}
  83. 		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));
  84. 		set(0,N[i].second,-1999999999);
  85. 		set(1,N[i].second,-1999999999);
  86. 		set(2,N[i].second,-1999999999);
  87. 	}
  88. //	printf("%lld %lld\n",ret,ad);
  89. 	return ret+ad;
  90. }
  91. int main(){
  92. 	int a,b,c;
  93. 	scanf("%d%d%d",&a,&b,&c);
  94. 	n=c;
  95. 	for(int i=0;i<c;i++)scanf("%d%d",&dat[i].first,&dat[i].second);
  96. 	long long ret=0;
  97. 	p=a;
  98. 	q=b;
  99. 	for(int j=0;j<4;j++){
  100. 		ret=max(ret,solve());
  101. 		for(int i=0;i<c;i++){
  102. 			dat[i]=make_pair(dat[i].second,p+1-dat[i].first);
  103. 		}
  104. 		swap(p,q);
  105. 	}
  106. 	printf("%lld\n",ret);
  107. }
Runtime error #stdin #stdout 0s 13352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2o5t4U
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!