fork download
  1. ///If you feel hard-headed ?
  2. ///Take it easy, you may don't have to do it
  3. ///PPAP_1264589
  4. #include <bits/stdc++.h>
  5. #pragma GCC optimize("Ofast")
  6. #pragma GCC optimize ("unroll-loops")
  7. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  8.  
  9. #define Task "C"
  10. #define ll long long
  11. #define bit(x,i) ((x >> i) & 1)
  12. #define stt(x,i) (x & (1 << i))
  13. #define trail0(x) (x & (-x))
  14. #define up(i,a,b) for (int i = (a); i <= (b); i++)
  15. #define down(i,a,b) for (int i = (a); i >= (b); i--)
  16. #define MOD 1000000007
  17. #define base 311
  18. #define pii pair<int, int>
  19. #define f first
  20. #define s second
  21. using namespace std;
  22.  
  23. const int maxn = 501;
  24. int n,m;
  25. int u,v,p,q;
  26. int sp[9][9][maxn][maxn];
  27.  
  28.  
  29. void Init(){
  30. cin >> n >> m;
  31. up(i, 1, n){
  32. up(j, 1, m){
  33. cin >> sp[0][0][i][j];
  34. }
  35. }
  36.  
  37. up(u, 1, n){
  38. up(j, 1, 8){
  39. for (int v = 1; v + (1 << j) - 1 <= m; v++){
  40. sp[0][j][u][v] = min(sp[0][j-1][u][v], sp[0][j-1][u][v + (1 << (j-1))]);
  41. }
  42. }
  43. }
  44.  
  45. up(i, 1, 8){
  46. up(j, 0, 8){
  47. for (int u = 1; u + (1 << i) - 1 <= n; u++){
  48. for (int v = 1; v + (1 << j) - 1 <= m; v++){
  49. sp[i][j][u][v] = min(sp[i-1][j][u][v], sp[i-1][j][u + (1 << (i-1))][v]);
  50. }
  51. }
  52. }
  53. }
  54. }
  55.  
  56. void getmin(int u, int v, int p, int q){
  57. int k = log2(p-u+1); //length of row
  58. int l = log2(q-v+1); //length of column
  59. int r = p - (1 << k) + 1;
  60. int s = q - (1 << l) + 1;
  61. int m1 = sp[k][l][u][v];
  62. int m2 = sp[k][l][u][s];
  63. int m3 = sp[k][l][r][v];
  64. int m4 = sp[k][l][r][s];
  65.  
  66. cout << min(min(min(m1, m2), m3), m4) << "\n";
  67. }
  68.  
  69.  
  70. signed main (){
  71. ios_base::sync_with_stdio(false);
  72. cin.tie(0);
  73. cout.tie(0);
  74. Init();
  75. int tt;
  76. cin >> tt;
  77. while (tt--){
  78. cin >> u >> v >> p >> q;
  79. getmin(u,v,p,q);
  80. }
  81. return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 9816KB
stdin
3 3
3 4 5
2 3 4
5 4 3
3
1 1 2 2
1 2 1 3
1 2 3 2
stdout
2
4
3