fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. using namespace std;
  4. int segtree[3][1048576];
  5. pair<int,int> dat[100000];
  6. int y[300001];
  7. pair<int,int>note[300001];
  8. pair<int,int>note2[300001];
  9. void set(int a,int b,int c){
  10. 	b+=524288;
  11. 	segtree[a][b]=c;
  12. 	b/=2;
  13. 	while(b){
  14. 		segtree[a][b]=max(segtree[a][b*2],segtree[a][b*2+1]);
  15. 		b/=2;
  16. 	}
  17. }
  18. int query(int a,int b,int c,int d,int e,int f){
  19. 	if(c<0||c>524287||d<0||d>524287||c>d)return -1999999999;
  20. 	if(d<a||b<c)return -1999999999;
  21. 	if(c<=a&&b<=d)return segtree[f][e];
  22. 	return max(query(a,(a+b)/2,c,d,e*2,f),query((a+b)/2+1,b,c,d,e*2+1,f));
  23. }
  24. int H,W,N;
  25. int solve(){
  26. 	for(int i=0;i<3;i++)
  27. 		for(int j=0;j<1048576;j++)
  28. 			segtree[i][j]=0;
  29. 	std::sort(dat,dat+N);
  30. 	for(int i=0;i<N;i++){
  31. 		y[i*3]=dat[i].second;
  32. 		y[i*3+1]=dat[i].second-1;
  33. 		y[i*3+2]=dat[i].second+1;
  34. 		note[i*3]=make_pair(dat[i].second,1);
  35. 		note[i*3+1]=make_pair(dat[i].second-1,0);
  36. 		note[i*3+2]=make_pair(dat[i].second+1,0);
  37. 		note2[i*3]=make_pair(dat[i].second,1);
  38. 		note2[i*3+1]=make_pair(dat[i].second-1,2);
  39. 		note2[i*3+2]=make_pair(dat[i].second+1,2);
  40. 	}
  41. 	std::sort(y,y+N*3);
  42. 	std::sort(note,note+N*3);
  43. 	std::sort(note2,note2+N*3);
  44. 	int SUM=y[0]-1;
  45. 	for(int i=0;i<N*3;i++){
  46. 		if(y[i]>=0&&y[i]<W&&(i==0||y[i-1]!=y[i])){
  47. 			set(0,i,0);
  48. 			set(1,i,SUM);
  49. 		}else{
  50. 			set(1,i,-1999999999);
  51. 			set(0,i,-1999999999);
  52. 		}
  53. 		//if(y[i]>=0&&y[i]<W&&(i==0||y[i-1]!=y[i])&&note2[i].second==1)set(0,i,0);
  54. 		//else set(0,i,-1999999999);
  55. 		SUM+=max(0,y[i+1]-y[i]-(note[i].second));
  56. 	}
  57. 	SUM=W-y[N*3-1];
  58. 	for(int i=N*3-1;i>=0;i--){
  59. 	//	printf("%d ",SUM);
  60. 		if(y[i]>=0&&y[i]<W&&(i==0||y[i]!=y[i-1]))set(2,i,SUM);
  61. 		else set(2,i,-1999999999);
  62. 		if(i)SUM+=max(0,y[i]-y[i-1]-(2-note2[i].second));
  63. 	}
  64. 	int ret=0;
  65. 	int mi=0;
  66. 	for(int i=0;i<N;i++){
  67. 		int L=upper_bound(dat,dat+N,make_pair(dat[i].first-1,1999999999))-lower_bound(dat,dat+N,make_pair(dat[i].first-1,0));
  68. 		int S;
  69. 		if(L==0){
  70. 			S=query(0,524287,0,N-1,1,0);
  71. 			if(S==0)ret=max(ret,S+dat[i].first-2-mi);
  72. 		}else if(L==1){
  73. 			int t=dat[lower_bound(dat,dat+N,make_pair(dat[i].first-1,0))-dat].second;
  74. 			int Y=lower_bound(y,y+N*3,t)-y;
  75. 			S=max(query(0,524287,0,Y,1,1),query(0,524287,Y,N*3-1,1,2));
  76. 			if(S>=0)ret=max(ret,S+dat[i].first-1-mi);
  77. 		}else{
  78. 			int t2=dat[upper_bound(dat,dat+N,make_pair(dat[i].first-1,1999999999))-dat-1].second;
  79. 			int t1=dat[lower_bound(dat,dat+N,make_pair(dat[i].first-1,0))-dat].second;
  80. 			int Y1=lower_bound(y,y+N*3,t1)-y;
  81. 			int Y2=lower_bound(y,y+N*3,t2)-y;
  82. 			S=max(max(query(0,524287,0,Y1,1,1),query(0,524287,Y2,N*3-1,1,2)),query(0,524287,Y1,Y2,1,0));
  83. 			if(S>=0)ret=max(ret,S+dat[i].first-1-mi);
  84. 		}
  85. 		int at=lower_bound(y,y+N*3,dat[i].second)-y;
  86. 		//printf("%d:%d,%d ",dat[i].first,S,dat[i].first-mi-(L?1:2));
  87. 		set(0,at,-1999999999);
  88. 		set(1,at,-1999999999);
  89. 		set(2,at,-1999999999);
  90. 		if(dat[i].first!=dat[i+1].first)mi++;
  91. 	}
  92. 	return ret;
  93. }
  94. int main(){
  95. 	int a,b,c;
  96. 	scanf("%d%d%d",&a,&b,&c);
  97. 	H=a;
  98. 	W=b;
  99. 	N=c;
  100. 	for(int i=0;i<c;i++){
  101. 		int d,e;
  102. 		scanf("%d%d",&d,&e);
  103. 		dat[i]=make_pair(d,e);
  104. 		y[i]=e;
  105. 	}
  106. 	std::sort(dat,dat+c);
  107. 	std::sort(y,y+c);
  108. 	int p=a-1;
  109. 	int q=b-1;
  110. 	for(int i=1;i<c;i++){
  111. 		if(dat[i].first!=dat[i-1].first)p--;
  112. 		if(y[i]!=y[i-1])q--;
  113. 	}
  114. 	long long NC=(long long)p*(long long)q;
  115. 	int val=0;
  116. 	for(int i=0;i<4;i++){
  117. 		int V=solve();
  118. 	//	printf("%d\n",V);
  119. 		val=max(val,V);
  120. 		for(int j=0;j<c;j++){
  121. 			dat[j]=make_pair(W-dat[j].second+1,dat[j].first);
  122. 		}
  123. 		swap(H,W);
  124. 	}
  125. //	printf("%lld %d\n",NC,val);
  126. 	printf("%lld\n",NC+val);
  127. }
Runtime error #stdin #stdout 0.03s 22280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cylr2l
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!