#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 200005;
int arr[4][2]={
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
int biggest_stadium(int n, std::vector<std::vector<int>> a)
{
vector<vector<int>> U(n, vector<int>(n));
vector<vector<int>> U2(n, vector<int>(n));
vector<vector<int>> L(n, vector<int>(n));
vector<vector<int>> L2(n, vector<int>(n));
vector<vector<int>> R2(n, vector<int>(n));
vector<vector<int>> pref(n, vector<int>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
pref[i][j] = a[i][j] == 0;
if(i > 0) pref[i][j] += pref[i - 1][j];
if(j > 0) pref[i][j] += pref[i][j - 1];
if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
if(i == 0){
if(a[i][j] == 1) U[i][j] = i;
else U[i][j] = -1;
}else{
if(a[i][j] == 1){
if(a[i - 1][j] == 1) U[i][j] = U[i - 1][j];
else U[i][j] = i;
}else{
U[i][j] = -1;
}
}
if(j == 0){
if(a[i][j] == 1) L[i][j] = j;
else L[i][j] = -1;
}else{
if(a[i][j] == 1){
if(a[i][j - 1] == 1) L[i][j] = L[i][j - 1];
else L[i][j] = j;
}else{
L[i][j] = -1;
}
}
if(i == 0){
if(a[i][j] == 0) U2[i][j] = i;
else U2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i - 1][j] == 0) U2[i][j] = U2[i - 1][j];
else U2[i][j] = i;
}else{
U2[i][j] = -1;
}
}
if(j == 0){
if(a[i][j] == 0) L2[i][j] = j;
else L2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i][j - 1] == 0) L2[i][j] = L2[i][j - 1];
else L2[i][j] = j;
}else{
L2[i][j] = -1;
}
}
}
for(int j = n-1; j >= 0; --j){
if(j == n-1){
if(a[i][j] == 0) R2[i][j] = j;
else R2[i][j] = -1;
}else{
if(a[i][j] == 0){
if(a[i][j + 1] == 0) R2[i][j] = R2[i][j + 1];
else R2[i][j] = j;
}else{
R2[i][j] = -1;
}
}
}
}
queue<pair<int, int>> q;
vector<vector<bool>> vis(n, vector<bool>(n));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j] == 0){
q.push({i, j});
vis[i][j] = 1;
break;
}
}
if(q.size()) break;
}
int sz = 0;
while(!q.empty()){
int x = q.front().ff;
int y = q.front().ss;
q.pop();
for(int i = 0; i < 4; ++i){
int nx = x + arr[i][0];
int ny = y + arr[i][1];
if(nx >= 0 && ny >= 0 && nx < n && ny < n && !vis[nx][ny] && a[nx][ny] == 0){
vis[nx][ny] = 1;
q.push({nx, ny});
}
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(a[i][j] == 0 && vis[i][j] == 0){
return 0;
}
if(a[i][j] == 1) continue;
++sz;
if(i > 0){
if(a[i - 1][j] == 1){
int pos = U[i - 1][j];
if(pos > 0 && a[pos - 1][j] == 0){
return 0;
}
}
}
if(j > 0){
if(a[i][j - 1] == 1){
int pos = L[i][j - 1];
if(pos > 0 && a[i][pos - 1] == 0){
return 0;
}
}
}
int lx = L2[i][j];
int rx = R2[i][j];
int dx = U2[i][j];
// dx - 1, lx - 1
// dx - 1, n - 1 / dx - 1, rx
if(dx > 0 && lx > 0){
if(pref[dx - 1][lx - 1] > 0) return 0;
}
if(dx > 0){
if(pref[dx - 1][n - 1] - pref[dx - 1][rx] > 0) return 0;
}
}
}
return sz;
}
