fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN = 2e3+5;
  11.  
  12. int n, m, k, a[maxN][maxN], pref[maxN][maxN], hieu_hang[maxN][maxN], hieu_cot[maxN][maxN], pref_hang[maxN][maxN], pref_cot[maxN][maxN];
  13.  
  14. void solve()
  15. {
  16.  
  17. }
  18.  
  19. int32_t main()
  20. {
  21. 	freopen("MAXSQR.INP", "r", stdin);
  22. 	freopen("MAXSQR.OUT", "w", stdout);
  23. 	ios_base::sync_with_stdio(0); cin.tie(0);
  24. 	cin>>n>>m>>k;
  25. 	for(int i=1; i<=k; i+=1)
  26. 	{
  27. 		int lx, rx, ly, ry; 
  28. 		cin>>lx>>rx>>ly>>ry;
  29. 		pref[lx][rx]++;
  30. 		pref[lx][ry+1]--;
  31. 		pref[ly+1][rx]--;
  32. 		pref[ly+1][ry+1]++;
  33. 	}
  34. 	for(int i=1; i<=n; i+=1)
  35. 	{
  36. 		for(int j=1; j<=m; j+=1) pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + pref[i][j];
  37. 	}
  38. 	// for(int i=1; i<=n; i+=1)
  39. 	// {
  40. 	// 	for(int j=1; j<=m; j+=1) cout<<pref[i][j]<<" "; cout<<'\n';
  41. 	// }
  42. 	for(int i=1; i<=n; i+=1)
  43. 	{
  44. 		for(int j=1; j<=m; j+=1) hieu_hang[i][j] = pref[i][j] - pref[i][j-1];
  45. 	}
  46. 	for(int j=1; j<=m; j+=1)
  47. 	{
  48. 		for(int i=1; i<=n; i+=1) hieu_cot[i][j] = pref[i][j] - pref[i-1][j];
  49. 	}
  50. 	for(int i=1; i<=n; i+=1)
  51. 	{
  52. 		for(int j=1; j<=m; j+=1)
  53. 		{
  54. 			if(hieu_hang[i][j]) hieu_hang[i][j] = 1;
  55. 		}
  56. 	}
  57. 	for(int j=1; j<=m; j+=1)
  58. 	{
  59. 		for(int i=1; i<=n; i+=1)
  60. 		{
  61. 			if(hieu_cot[i][j]) hieu_cot[i][j] = 1;
  62. 		}
  63. 	}
  64. 	for(int i=1; i<=n; i+=1)
  65. 	{
  66. 		for(int j=1; j<=m; j+=1) pref_hang[i][j] = pref_hang[i-1][j] + pref_hang[i][j-1] - pref_hang[i-1][j-1] + hieu_hang[i][j];
  67. 	}
  68. 	for(int i=1; i<=n; i+=1)
  69. 	{
  70. 		for(int j=1; j<=m; j+=1) pref_cot[i][j] = pref_cot[i-1][j] + pref_cot[i][j-1] - pref_cot[i-1][j-1] + hieu_cot[i][j];
  71. 	}
  72. 	// cout<<"\n\n\n";
  73. 	// for(int i=1; i<=n; i+=1)
  74. 	// {
  75. 	// 	for(int j=1; j<=m; j+=1) cout<<hieu_cot[i][j]<<" "; cout<<'\n';
  76. 	// }
  77. 	// cout<<"\n\n\n";
  78. 	// for(int i=1; i<=n; i+=1)
  79. 	// {
  80. 	// 	for(int j=1; j<=m; j+=1) cout<<hieu_hang[i][j]<<" "; cout<<'\n';
  81. 	// }
  82. 	int l = 1, r = min(n, m), ans = 0;
  83. 	while(r-l>=0)
  84. 	{
  85. 		int mid = (l+r)>>1;
  86. 		bool check = 0;
  87. 		for(int i=1; i<=n; i+=1)
  88. 		{
  89. 			if(check) break;
  90. 			for(int j=1; j<=m; j+=1)
  91. 			{
  92. 				int mid1 = mid-1;
  93. 				int j1 = j+1, i1 = i+1;
  94. 				if(i+mid1 > n || j+mid1>m) continue;
  95. 				int tmp1 = pref_hang[i+mid1][j+mid1] + pref_hang[i-1][j1-1] - pref_hang[i-1][j+mid1] - pref_hang[i+mid1][j1-1];
  96. 				int tmp2 = pref_cot[i+mid1][j+mid1] + pref_cot[i1-1][j-1] - pref_cot[i1-1][j+mid1] - pref_cot[i+mid1][j-1];
  97. 				if(tmp1 == tmp2 && tmp1 == 0) 
  98. 				{
  99. 					// cout<<mid<<" "<<i<<" "<<j<<'\n';
  100. 					check = 1;
  101. 					break;
  102. 				}
  103. 			}
  104. 		}
  105. 		if(check || mid <= 1) l = mid+1, ans = mid;
  106. 		else r = mid-1;
  107. 	}
  108. 	cout<<ans<<'\n';
  109. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UBBhnZ
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!