#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
template <typename T, int64_t N>
struct FenwickTree
{
T t[N][N];
void update(int64_t i, int64_t j, T x)
{
++i;
while (i <= N)
{
int64_t k = j + 1;
while (k <= N)
{
t[i - 1][k - 1] += x;
k += k & -k;
}
i += i & -i;
}
}
T prefix_sum(int64_t i, int64_t j)
{
T x = 0;
++i;
while (i)
{
int64_t k = j + 1;
while (k)
{
x += t[i - 1][k - 1];
k -= k & -k;
}
i -= i & -i;
}
return x;
}
T range_sum(int64_t i1, int64_t i2, int64_t j1, int64_t j2)
{
return prefix_sum(i2, j2) - (i1 ? prefix_sum(i1 - 1, j2) : 0) - (j1 ? prefix_sum(i2, j1 - 1) : 0) +
(i1 && j1 ? prefix_sum(i1 - 1, j1 - 1) : 0);
}
};
constexpr size_t R = 3000;
FenwickTree<int, R> tree;
int k;
vector<pair<int, int>> order;
int parallel_bsearch(vector<pair<int, int>> const &q, int H, int W, int a, int b)
{
if (a == b)
return a;
int const mid = (a + b) / 2;
while (k < mid)
++k, tree.update(order[k].first, order[k].second, 1);
while (k > mid)
tree.update(order[k].first, order[k].second, -1), --k;
vector<pair<int, int>> left_q, right_q;
for (auto const &[i, j] : q)
{
int num_leq = tree.range_sum(i, i + H - 1, j, j + W - 1);
if (num_leq < (H * W) / 2 + 1)
right_q.emplace_back(i, j);
else
left_q.emplace_back(i, j);
}
if (!left_q.empty())
return parallel_bsearch(left_q, H, W, a, (a + b) / 2);
return parallel_bsearch(right_q, H, W, (a + b) / 2 + 1, b);
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
order.resize(R * C + 1);
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
order[Q[i][j]] = {i, j};
vector<pair<int, int>> queries;
for (int i = 0; i < R - H + 1; ++i)
for (int j = 0; j < C - W + 1; ++j)
queries.emplace_back(i, j);
return parallel_bsearch(queries, H, W, 1, R * C);
}
