MSQUARE (CSPTST 2022-2023)

#define task "MSQUARE"
#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
#include <queue>
#include <set>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e6 + 5;
int m, n;
vector<int> b[N];
vector<pair<int, int>> s[N * 2];
vector<int> l[N * 2], r[N * 2];

void Read()
{
    cin >> m >> n;

    b[0].resize(n + 1, 0);

    for (int i = 1; i <= m; ++i)
    {
        b[i].resize(n + 1, 0);

        for (int j = 1; j <= n; ++j)
        {
            cin >> b[i][j];
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
        }
    }
}

#define Cal(x, y, z, t) (b[z][t] - b[x - 1][t] - b[z][y - 1] + b[x - 1][y - 1])

int Get(const vector<pair<int, int>> &a)
{
    priority_queue<pair<int, int>> q;
    set<int> s;

    int ans = 0;

    for (int i = 0; i < (int)a.size(); ++i)
    {
        q.emplace(-(a[i].second + i - 1), i);
        s.insert(i);

        while (!q.empty() && -q.top().first < i)
        {
            s.erase(q.top().second);
            q.pop();
        }

        if (!q.empty())
        {
            auto x = s.lower_bound(i - a[i].first + 1);
            if (x != s.end())
                ans = max(ans, i - (*x) + 1);
        }
    }

    return ans;
}

void Solve()
{

    /*
                1
                ^
                |
         2 <- (i, j) -> 3
                |
                v
                4
     */
    // Tinh (1-3) va (2-4)

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
        {
            //(1-3)
            int l = 1, mid, h = min(i, n - j + 1);
            while (l <= h)
            {
                mid = (l + h) / 2;
                if (Cal(i - mid + 1, j, i, j) == mid && Cal(i, j, i, j + mid - 1) == mid)
                    l = mid + 1;
                else
                    h = mid - 1;
            }

            int x = h;

            // (2-4)
            l = 1, h = min(j, m - i + 1);
            while (l <= h)
            {
                mid = (l + h) / 2;
                if (Cal(i, j - mid + 1, i, j) == mid && Cal(i, j, i + mid - 1, j) == mid)
                    l = mid + 1;
                else
                    h = mid - 1;
            }

            int y = h;

            s[i + j - 1].emplace_back(x, y);
        }

    int ans = 0;

    for (int i = 1; i < m + n; ++i)
        ans = max(ans, Get(s[i]));

    cout << ans * ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}