fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. const int N = 101;
  7. int n, m, q, cum[501][N][N], g[N][N];
  8.  
  9. int main(int argc, char **argv) {
  10. 	int T;
  11. 	scanf("%d", &T);
  12. 	while (T-- != 0) {
  13. 		scanf("%d%d%d", &n, &m, &q);
  14. 		int mx = 0;
  15. 		for (int i = 1; i <= n; ++i)
  16. 			for (int j = 1; j <= m; ++j) {
  17. 				scanf("%d", &g[i][j]);
  18. 				mx = max(mx, g[i][j]);
  19. 				for (int k = 1; k <= 500; ++k)
  20. 					cum[k][i][j] = cum[k][i][j - 1] + cum[k][i - 1][j] - cum[k][i - 1][j - 1] + (g[i][j] == k);
  21. 			}
  22. 		for (int i = 2; i <= mx; ++i)
  23. 			for (int j = 1; j <= n; ++j)
  24. 				for (int k = 1; k <= m; ++k)
  25. 					cum[i][j][k] += cum[i - 1][j][k];
  26. 		int a, b, c, d;
  27. 		while (q-- != 0) {
  28. 			scanf("%d%d%d%d", &a, &b, &c, &d);
  29. 			int L = (c - a + 1) * (d - b + 1);
  30. 			int medIdx = (L + 1) >> 1;
  31. 			int l = 1, r = mx, res = 0;
  32. 			while (l <= r) {
  33. 				int mid = (l + r) >> 1;
  34. 				int v = cum[mid][c][d] - cum[mid][a - 1][d] - cum[mid][c][b - 1] + cum[mid][a - 1][b - 1];
  35. 				if (v < medIdx) {
  36. 					res = mid;
  37. 					l = mid + 1;
  38. 				} else
  39. 					r = mid - 1;
  40. 			}
  41. 			printf("%d\n", res + 1);
  42. 		}
  43. 	}
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 5672KB
comments (?)
stdin
copy 
1
4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 2
1 2 3 3
1 3 4 3
stdout
copy 
2
6
7
https://ideone.com/WEkeVH
language:
C++14 (gcc 8.3)
created:
6 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!