Advertisement
royalsflush

Grapevine errado

Jul 1st, 2012
49
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int n,m;
  6. int map[510][510];
  7. int q,l,u;
  8.  
  9. inline int fits(int i, int j, int k) {
  10.     return map[i+k][j+k]>=l &&
  11.             map[i+k][j+k]<=u;
  12. }
  13.  
  14. inline bool inMap(int i, int j) {
  15.     return i>=0 && i<n && j>=0 && j<m;
  16. }
  17.  
  18. int biggest(int i, int j) {
  19.     int low, beg=0, end=min(n-i,m-j)-1;
  20.     int tmpEnd;
  21.  
  22.     while (!inMap(i+end-1,j+end-1))
  23.         end++;
  24.     while (inMap(i+end+1,j+end+1))
  25.         end++;
  26.  
  27.     tmpEnd=end;
  28.  
  29.     while (beg<end) {
  30.         int mid=(beg+end)/2;
  31.  
  32.         if (fits(i,j,mid)) end=mid;
  33.         else beg=mid+1;
  34.     }
  35.  
  36.     if (!fits(i,j,beg))
  37.         return 0;
  38.  
  39.     low=beg;
  40.     beg=0, end=tmpEnd;
  41.  
  42.     while (beg<end) {
  43.         int mid=(beg+end+1)/2;
  44.  
  45.         if (fits(i,j,mid)) beg=mid;
  46.         else end=mid-1;
  47.     }
  48.  
  49.     return beg-low+1;  
  50. }
  51.  
  52. int main() {
  53.     while (1) {
  54.         scanf("%d %d", &n,&m);
  55.         if (!n && !m)
  56.             break;
  57.  
  58.         for (int i=0; i<n; i++)
  59.             for (int j=0; j<m; j++)
  60.                 scanf("%d", &map[i][j]);
  61.  
  62.         scanf("%d", &q);
  63.  
  64.         while (q--) {
  65.             scanf("%d %d", &l,&u);
  66.             int big=0;
  67.  
  68.             for (int i=0; i<n; i++)
  69.                 big=max(big,biggest(i,0));
  70.            
  71.             for (int i=0; i<m; i++)
  72.                 big=max(big,biggest(0,i));
  73.  
  74.             printf("%d\n", big);
  75.         }
  76.         printf("-\n");
  77.     }
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement