fork download
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. const int N = 100 + 3, M = 500 + 5;
  5. int n, m, q, a, b, c, d, v[N][N], freq[N][N][M], f[M], sz;
  6. int main() {
  7. int t;
  8. scanf("%d", &t);
  9. while(t--) {
  10. scanf("%d%d%d", &n, &m, &q);
  11. for(int i=1; i<=n; ++i)
  12. for(int j=1; j<=m; ++j) {
  13. scanf("%d", &v[i][j]);
  14. for(int k=1; k<=500; ++k)
  15. freq[i][j][k] = freq[i-1][j][k] + freq[i][j-1][k]
  16. - freq[i-1][j-1][k] + (v[i][j] == k);
  17. }
  18. while(q--) {
  19. scanf("%d%d%d%d", &a, &b, &c, &d);
  20. sz = (c-a+1)*(d-b+1) + 1;
  21. sz /= 2;
  22. for(int i=1; i<=500; ++i) {
  23. f[i] = freq[c][d][i] - freq[a-1][d][i]
  24. - freq[c][b-1][i] + freq[a-1][b-1][i];
  25. if(f[i] == 0) continue;
  26. sz -= f[i];
  27. if(sz <= 0) {
  28. sz = i;
  29. break;
  30. }
  31. }
  32. printf("%d\n", sz);
  33. }
  34. }
  35. return 0;
  36. }
Success #stdin #stdout 0s 4392KB
stdin
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
2
6
7