#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int nt = 1;
vector<vector<int>> st_h, st_v;
int getvrange(int l, int r, int k, int x, int y, int i)
{
if (l > r) swap(l, r);
if (r < x || l > y) return 0;
if (x >= l && y <= r) return st_v[i][k];
int c = (x + y) / 2;
return getvrange(l, r, k*2, x, c, i) | getvrange(l, r, k*2|1, c+1, y, i);
}
int gethrange(int l, int r, int k, int x, int y, int i)
{
if (l > r) swap(l, r);
if (r < x || l > y) return 0;
if (x >= l && y <= r) return st_h[i][k];
int c = (x + y) / 2;
return gethrange(l, r, k*2, x, c, i) | gethrange(l, r, k*2|1, c+1, y, i);
}
int biggest_stadium(int N, vector<vector<int>> F)
{
int res = 0;
while (nt < N)
nt *= 2;
st_v = st_h = vector<vector<int>>(N, vector<int>(2*nt));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
st_h[i][nt + j] = F[i][j];
st_v[i][nt + j] = F[j][i];
}
for (int j = nt - 1; j >= 1; j--)
{
st_h[i][j] = st_h[i][j*2] | st_h[i][j*2|1];
st_v[i][j] = st_v[i][j*2] | st_v[i][j*2|1];
}
}
vector<pair<int, int>> vpi;
for (int y = 0; y < N; y++)
{
for (int x = 0; x < N; x++)
{
if (!F[y][x])
vpi.push_back({x, y});
}
}
for (int i = 0; i < vpi.size(); i++)
{
int x, y;
tie(x, y) = vpi[i];
for (int j = i+1; j < vpi.size(); j++)
{
int nx, ny;
tie(nx, ny) = vpi[j];
bool b1 = getvrange(y, ny, 1, 0, nt - 1, x) || gethrange(x, nx, 1, 0, nt - 1, ny);
bool b2 = getvrange(y, ny, 1, 0, nt - 1, nx) || gethrange(x, nx, 1, 0, nt - 1, y);
cerr << x << " " << y << " : " << nx << " " << ny << " = " << b1 << ", " << b2 << "\n";
if (b1 && b2)
return -1;
}
}
return vpi.size();
}
