fork(1) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
2
4
3
https://ideone.com/iTSAGV
language:
C++14 (gcc 8.3)
created:
2 years 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!