Guest User

Untitled

a guest
Jan 8th, 2015
226
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <list>
  2. #include <map>
  3. #include <set>
  4. #include <deque>
  5. #include <stack>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <sstream>
  9. #include <iostream>
  10. #include <iomanip>
  11. #include <cstdio>
  12. #include <cmath>
  13. #include <cstdlib>
  14. #include <memory.h>
  15. #include <ctime>
  16. #include <bitset>
  17.  
  18. using namespace std;
  19.  
  20. #define ABS(a) ((a>0)?a:-(a))
  21. #define MIN(a,b) ((a<b)?(a):(b))
  22. #define MAX(a,b) ((a<b)?(b):(a))
  23. #define FOR(i,a,n) for (int i=(a);i<(n);++i)
  24. #define FI(i,n) for (int i=0; i<(n); ++i)
  25. #define pnt pair <int, int>
  26. #define mp make_pair
  27. #define PI 3.1415926535897
  28. #define MEMS(a,b) memset(a,b,sizeof(a))
  29. #define LL long long
  30. #define U unsigned
  31.  
  32. const int N = 401;
  33. int max1[N][N][10][10];
  34. int min1[N][N][10][10];
  35. int a[N][N];
  36. int st[410];
  37.  
  38. int main()
  39. {
  40. #ifdef Fcdkbear
  41.     freopen("in.txt", "r", stdin);
  42.     //freopen("out.txt", "w", stdout);
  43.     double beg = clock();
  44. #endif
  45.  
  46.     int n, m, q;
  47.     scanf("%d%d%d", &n, &m, &q);
  48.     FOR(i, 0, n)
  49.         FOR(j, 0, m)
  50.         scanf("%d", &a[i][j]);
  51.     int k1 = 1, k2 = 1;
  52.     int st1 = 0, st2 = 0;
  53.     while (k1 + k1 <= m)
  54.     {
  55.         k1 += k1;
  56.         st1++;
  57.     }
  58.     while (k2 + k2 <= n)
  59.     {
  60.         k2 += k2;
  61.         st2++;
  62.     }
  63.     FOR(i,0,n)
  64.         FOR(j, 0, m)
  65.         {
  66.             min1[i][j][0][0] = max1[i][j][0][0] = a[i][j];
  67.         }
  68.     FOR(i, 0, n)
  69.     {
  70.         FOR(k, 1, st1 + 1)
  71.         {
  72.             int val = (1 << k);
  73.             int nval = val / 2;
  74.             FOR(j, 0, m)
  75.             {
  76.                 if (j + val > m)
  77.                     break;
  78.                 max1[i][j][k][0] = MAX(max1[i][j][k - 1][0], max1[i][j + nval][k - 1][0]);
  79.                 min1[i][j][k][0] = MIN(min1[i][j][k - 1][0], min1[i][j + nval][k - 1][0]);
  80.             }
  81.         }
  82.     }
  83.     FOR(j, 0, m)
  84.     {
  85.         FOR(k, 1, st2 + 1)
  86.         {
  87.             int val = (1 << k);
  88.             int nval = val / 2;
  89.             FOR(i, 0, n)
  90.             {
  91.                 if (i + val > n)
  92.                     break;
  93.                 max1[i][j][0][k] = MAX(max1[i][j][0][k - 1], max1[i + nval][j][0][k - 1]);
  94.                 min1[i][j][0][k] = MIN(min1[i][j][0][k - 1], min1[i + nval][j][0][k - 1]);
  95.             }
  96.         }
  97.     }
  98.     FOR(k1, 1, st1 + 1)
  99.     {
  100.         int val1 = (1 << k1);
  101.         int nval1 = val1 / 2;
  102.         FOR(k2, 1, st2 + 1)
  103.         {
  104.             int val2 = (1 << k2);
  105.             int nval2 = val2 / 2;
  106.             FOR(i, 0, n)
  107.             {
  108.                 FOR(j, 0, m)
  109.                 {
  110.                     if ((j + val1 > m) || (i + val2 > n))
  111.                         continue;
  112.                     max1[i][j][k1][k2] = MAX(MAX(max1[i][j][k1 - 1][k2 - 1], max1[i + nval2][j][k1 - 1][k2 - 1]), MAX(max1[i][j+nval1][k1 - 1][k2 - 1], max1[i + nval2][j+nval1][k1 - 1][k2 - 1]));
  113.                     min1[i][j][k1][k2] = MIN(MIN(min1[i][j][k1 - 1][k2 - 1], min1[i + nval2][j][k1 - 1][k2 - 1]), MIN(min1[i][j + nval1][k1 - 1][k2 - 1], min1[i + nval2][j + nval1][k1 - 1][k2 - 1]));
  114.                 }
  115.             }
  116.         }
  117.     }
  118.     st[1] = 0;
  119.     int c = 0;
  120.     FOR(i, 2, 401)
  121.     {
  122.         int v = (1 << c);
  123.         if (v + v < i)
  124.             c++;
  125.         st[i] = c;
  126.     }
  127.    
  128.     FOR(it, 0, q)
  129.     {
  130.         int val;
  131.         cin >> val;
  132.         LL res = 0;
  133.         FOR(i, 0, n)
  134.         {
  135.             FOR(j, 0, m)
  136.             {
  137.                 int down = n - 1;
  138.                 FOR(k, j, m)
  139.                 {
  140.                     while (down >= i)
  141.                     {
  142.                         int dx = down - i + 1;
  143.                         int dy = k - j + 1;
  144.                         int k1 = st[dy];
  145.                         int k2 = st[dx];
  146.                         int val1 = (1 << k1);
  147.                         int val2 = (1 << k2);
  148.                         int max11 = MAX(max1[i][j][k1][k2], max1[i][k-val1+1][k1][k2]);
  149.                         int max12 = MAX(max1[down - val2 + 1][j][k1][k2], max1[down - val2 + 1][k - val1 + 1][k1][k2]);
  150.                         int min11 = MIN(min1[i][j][k1][k2], min1[i][k - val1 + 1][k1][k2]);
  151.                         int min12 = MIN(min1[down - val2 + 1][j][k1][k2], min1[down - val2 + 1][k - val1 + 1][k1][k2]);
  152.                         int cmax = MAX(max11, max12);
  153.                         int cmin = MIN(min11, min12);
  154.                         if (cmax - cmin > val)
  155.                             down--;
  156.                         else
  157.                             break;
  158.                     }
  159.                     if (down < i)
  160.                         break;
  161.                     res += down - i + 1;
  162.                 }
  163.             }
  164.         }
  165.         cout << res << endl;
  166.     }
  167.  
  168. #ifdef Fcdkbear
  169.     double end = clock();
  170.     fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
  171. #endif
  172.     return 0;
  173. }
RAW Paste Data