Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2016
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.59 KB | None | 0 0
  1. //#include <bits/stdc++.h>
  2. #include <stdio.h>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <algorithm>
  6. #include <iostream>
  7. #define PI 3.14159265
  8. #define N 300+5
  9. #define ll long long
  10. #define INF 2147483647
  11. using namespace std;
  12. int st[N][N][9];//2^9>300
  13. int g[N][N],n,x1,Y1,x2,y2,m,level,nq,maxi,from,to;
  14.  
  15. void RMQ2d(int x1,int Y1,int x2,int y2){
  16. if(x1>x2) swap(x1,x2);
  17. from=min(Y1,y2);
  18. to=max(Y1,y2);
  19. level=log2(to-from+1);
  20. maxi=-9999;
  21. for(int i=x1;i<=x2;i++) maxi=max(maxi,max(st[i][from][level],st[i][to+1-(1<<level)][level]));//這裡不能從from加 要用to減是因為要分割的數組塊長度可能為奇數 且st[][]只記錄前標及長度 所以會出錯 例如分割1234567 錯的:1234 5678 對的:1234 4567
  22. }
  23. void build(){
  24. for(int i=0;i<n;i++){
  25. for(int j=0;j<m;j++) st[i][j][0]=g[i][j];
  26. for(int level=1;level<=log2(m);level++)
  27. for(int from=0;from+(1<<(level-1))-1<m;from++){//因為數組長最短=1 所以前標最大為from+(1<<(level-1))-1
  28. st[i][from][level]=max(st[i][from][level-1],st[i][from+(1<<(level-1))][level-1]);
  29. }
  30. }
  31. }
  32. int main(){
  33. while(scanf("%d%d",&n,&m)!=EOF){
  34. for(int i=0;i<n;i++)
  35. for(int j=0;j<m;j++) scanf("%d",&g[i][j]);
  36. build();
  37. scanf("%d",&nq);
  38. while(nq--){
  39. scanf("%d%d%d%d",&x1,&Y1,&x2,&y2);
  40. x1--; Y1--; x2--; y2--;
  41. RMQ2d(x1,Y1,x2,y2);
  42. if(g[x1][Y1]==maxi||g[x1][y2]==maxi||g[x2][Y1]==maxi||g[x2][y2]==maxi)
  43. printf("%d yes\n",maxi);
  44. else printf("%d no\n",maxi);
  45. }
  46. }
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement