fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. const int LIM = 3030;
  8.  
  9. template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
  10. template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
  11.  
  12. int r, c, h, w;
  13. int a[LIM][LIM];
  14.  
  15.  
  16. int subtask1() 
  17. { 
  18.     return r * c; 
  19. }
  20.  
  21.  
  22. int subtask2()
  23. { 
  24.     return (r * c + 1) / 2;
  25. }
  26.  
  27.  
  28. int value[LIM * LIM];
  29. int subtask3()
  30. {
  31.     int res = 0;
  32.     for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
  33.     {
  34.         for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
  35.         {
  36.             int p = 0;
  37.             for (int x = lx; x <= rx; ++x)
  38.                 for (int y = ly; y <= ry; ++y)
  39.                     value[++p] = a[x][y];
  40.  
  41.             sort(value + 1, value + p + 1);
  42.             maximize(res, value[(p + 1) / 2]);
  43.         }
  44.     }
  45.  
  46.     return res;
  47. }
  48.  
  49. /// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
  50.  
  51. int used[LIM * LIM];
  52. int subtask4()
  53. {
  54.     int timer = 0;
  55.     memset(used, 0, sizeof(used));
  56.  
  57.     int res = 0;
  58.     for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
  59.     {
  60.         for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
  61.         {
  62.             int mn = r * c;
  63.             int mx = 1;
  64.             ++timer;
  65.             for (int x = lx; x <= rx; ++x)
  66.             {
  67.                 for (int y = ly; y <= ry; ++y)
  68.                 {
  69.                     minimize(mn, a[x][y]);
  70.                     maximize(mx, a[x][y]);
  71.                     used[a[x][y]] = timer;
  72.                 }
  73.             }
  74.  
  75.             int cnt = (h * w + 1) / 2;
  76.             for (int v = mn; v <= mx; ++v)
  77.             {
  78.                 if (used[v] == timer)
  79.                 {
  80.                     if (--cnt == 0)
  81.                     {
  82.                         maximize(res, v);
  83.                         break;
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.     }
  89.  
  90.     return res;
  91. }
  92.  
  93.  
  94. int bit[LIM * LIM];
  95. void bit_construct()
  96. {
  97.     memset(bit, 0, sizeof(bit[0]) * (r * c + 1));
  98. }
  99.  
  100. void bit_update(int p, int v)
  101. {
  102.     for (; p <= r * c; p += p & -p)
  103.         bit[p] += v;
  104. }
  105.  
  106. int bit_query(int p)
  107. {
  108.     int res = 0;
  109.     for (; p >= 1; p -= p & -p)
  110.         res += bit[p];
  111.  
  112.     return res;
  113. }
  114.  
  115. int bit_median()
  116. {
  117.     int expected = (h * w + 1) / 2;
  118.     int upper = r * c - expected + 1;
  119.     int lower = expected;
  120.  
  121.     int res = -1;
  122.     for (int l = lower, r = upper; l <= r; )
  123.     {
  124.         int m = (l + r) >> 1;
  125.         if (bit_query(m) >= expected)
  126.         {
  127.             res = m;
  128.             r = m - 1;
  129.         }
  130.         else 
  131.         {
  132.             l = m + 1;
  133.         }
  134.     }
  135.  
  136.     return res;
  137. }
  138.  
  139. int subtask5()
  140. {
  141.     int res = 0;
  142.     for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
  143.     {
  144.         bit_construct();
  145.         for (int x = lx; x <= rx; ++x)
  146.             for (int y = 1; y <= w; ++y)
  147.                 bit_update(a[x][y], +1);   
  148.  
  149.         for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
  150.         {
  151.             maximize(res, bit_median());
  152.  
  153.             if (ry == c) break;
  154.             for (int x = lx; x <= rx; ++x)
  155.             {
  156.                 bit_update(a[x][ly + 0], -1);
  157.                 bit_update(a[x][ry + 1], +1);
  158.             }
  159.         }
  160.     }
  161.  
  162.     return res;
  163. }
  164.  
  165.  
  166. int bit2d[LIM][LIM];
  167. void bit2d_construct()
  168. {
  169.     for (int x = 1; x <= r; ++x)
  170.         memset(bit2d[x], 0, sizeof(bit2d[x][0]) * (c + 1));
  171. }
  172.  
  173. void bit2d_update(int x, int y, int v)
  174. {
  175.     for (int p = x; p <= r; p += p & -p)
  176.         for (int q = y; q <= c; q += q & -q)
  177.             bit2d[p][q] += v;
  178. }
  179.  
  180. int bit2d_query(int x, int y)
  181. {
  182.     int res = 0;
  183.     for (int p = x; p >= 1; p -= p & -p)
  184.         for (int q = y; q >= 1; q -= q & -q)
  185.             res += bit2d[p][q];
  186.  
  187.     return res;
  188. }
  189.  
  190. void bit2d_area_update(int x, int y, int u, int v, int k)
  191. {
  192.     bit2d_update(u, v, +k);
  193.     bit2d_update(u, y - 1, -k);
  194.     bit2d_update(x - 1, v, -k);
  195.     bit2d_update(x - 1, y - 1, +k);
  196. }
  197.  
  198. int bit2d_area_query(int x, int y, int u, int v)
  199. {
  200.     int res = 0;
  201.     res += bit2d_query(u, v);
  202.     res -= bit2d_query(u, y - 1);
  203.     res -= bit2d_query(x - 1, v);
  204.     res += bit2d_query(x - 1, y - 1);
  205.     return res;
  206. }
  207.  
  208. int testing(int value, int target)
  209. {
  210.     bit2d_construct();
  211.     for (int i = 1; i <= r; ++i)
  212.     {
  213.         for (int j = 1; j <= c; ++j)
  214.         {
  215.             if (a[i][j] >= value)
  216.                 bit2d_update(i, j, +1);
  217.  
  218.             if (i >= h && j >= w)
  219.             {
  220.                 int cnt = bit2d_area_query(i - h + 1, j - w + 1, i, j);
  221.                 if (cnt >= target)
  222.                     return true;
  223.             }
  224.         }
  225.     }
  226.  
  227.     return false;
  228. }
  229.  
  230. int subtask6()
  231. {
  232.     int expected = (h * w + 1) / 2;
  233.     int upper = r * c - expected + 1;
  234.     int lower = expected;
  235.  
  236.     int res = -1;
  237.     for (int l = lower, r = upper; l <= r; )
  238.     {
  239.         int m = (l + r) >> 1;
  240.         if (testing(m, expected))
  241.         {
  242.             maximize(res, m);
  243.             l = m + 1;
  244.         }
  245.         else 
  246.         {
  247.             r = m - 1;
  248.         }
  249.     }
  250.  
  251.     return res;
  252. }
  253.  
  254. int b[LIM][LIM];
  255. int check(int value, int target)
  256. {
  257.     for (int i = 1; i <= r; ++i)
  258.     {
  259.         for (int j = 1; j <= c; ++j)
  260.         {
  261.             b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
  262.             b[i][j] += (a[i][j] >= value);
  263.         }
  264.     }
  265.  
  266.     for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
  267.     {
  268.         for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
  269.         {
  270.             int cnt = b[rx][ry] - b[lx - 1][ry] - b[rx][ly - 1] + b[lx - 1][ly - 1];
  271.             if (cnt >= target)
  272.                 return true;
  273.         }
  274.     }
  275.  
  276.     return false;
  277. }
  278.  
  279. int subtask7()
  280. {
  281.     int expected = (h * w + 1) / 2;
  282.     int upper = r * c - expected + 1;
  283.     int lower = expected;
  284.  
  285.     int res = -1;
  286.  
  287.     for (int l = lower, r = upper; l <= r; )
  288.     {
  289.         int m = (l + r) >> 1;
  290.         if (check(m, expected))
  291.         {
  292.             maximize(res, m);
  293.             l = m + 1;
  294.         }
  295.         else 
  296.         {
  297.             r = m - 1;
  298.         }
  299.     }
  300.  
  301.     return res;
  302. }
  303.  
  304. int main()
  305. {
  306.     ios::sync_with_stdio(NULL);
  307.     cin.tie(NULL);
  308.  
  309.     cin >> r >> c >> h >> w;
  310.     if (h == 1 && w == 1) return cout << subtask1(), 0;
  311.     if (h == r && w == c) return cout << subtask2(), 0;
  312.     for (int i = 1; i <= r; ++i)
  313.         for (int j = 1; j <= c; ++j)
  314.             cin >> a[i][j];
  315.  
  316.     if (r <=   30 && c <=   30) return cout << subtask3(), 0;
  317.     if (r <=  100 && c <=  100) return cout << subtask4(), 0;
  318.     if (r <=  300 && c <=  300) return cout << subtask5(), 0;
  319.     if (r <= 1000 && c <= 1000) return cout << subtask6(), 0;
  320.     if (r <= 3000 && c <= 3000) return cout << subtask7(), 0;
  321.     return 0;
  322. }
Success #stdin #stdout 0.01s 7744KB
comments (?)
stdin 
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
stdout 
20
https://ideone.com/pzE1sR
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!