SHARE
TWEET

Grapevine AC

royalsflush Jul 1st, 2012 3 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. int n,m;
  6. int map[510][510];
  7. int q;
  8. int l,u;
  9.  
  10. inline bool fits(int i, int j, int k) {
  11.         return (map[i+k][j+k]>=l &&
  12.                         map[i+k][j+k]<=u);
  13. }
  14.  
  15. int biggest(int i, int j) {
  16.         int beg=0, end=min(n-i, m-j)-1;
  17.         int low;
  18.  
  19.         while (beg<end) {
  20.                 int mid=(beg+end)/2;
  21.  
  22.                 if (map[i+mid][j+mid]>=l) end=mid;
  23.                 else beg=mid+1;
  24.         }
  25.  
  26.         if (!fits(i,j,beg))
  27.                 return 0;
  28.  
  29.         low=beg;
  30.         beg=0, end=min(n-i,m-j)-1;
  31.  
  32.         while (beg<end) {
  33.                 int mid=(beg+end+1)/2;
  34.  
  35.                 if (map[i+mid][j+mid]<=u) beg=mid;
  36.                 else end=mid-1;
  37.         }
  38.  
  39.         return beg-low+1;
  40. }
  41.  
  42. int main() {
  43.         while (1) {
  44.                 scanf("%d %d", &n,&m);
  45.                 if (!n && !m)
  46.                         break;
  47.  
  48.                 for (int i=0; i<n; i++)
  49.                         for (int j=0; j<m; j++)
  50.                                 scanf("%d", &map[i][j]);
  51.  
  52.                 scanf("%d", &q);
  53.  
  54.                 while (q--) {
  55.                         scanf("%d %d", &l,&u);
  56.                         int big=0;                     
  57.  
  58.                         for (int i=0; i<n; i++)
  59.                                 big=max(biggest(i,0),big);
  60.                        
  61.                         for (int j=1; j<m; j++)
  62.                                 big=max(biggest(0,j),big);
  63.                         printf("%d\n", big);
  64.                 }
  65.                 printf("-\n");
  66.         }
  67.  
  68.         return 0;
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top