#include "soccer.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;
int N;
int arr[2005][2005];
int R[2005][2005],u[2005][2005],d[2005][2005];
int p = 4000;
struct Rect{
int rs,re,cs,ce,id,dp;
bool operator<(const Rect &r) const{
return array<int,3>{(cs-ce)*p + re-rs, rs*p+cs, id} < array<int,3>{(r.cs-r.ce)*p+r.re-r.rs, r.rs*p+r.cs, r.id};
}
bool operator==(const Rect &r) const{
return (rs==r.rs && re==r.re && cs==r.cs && ce==r.ce);
}
};
vector<Rect> rect;
struct Seg{
pair<int,int> arr[8001];
void update(int now, int s, int e, int &f, pair<int,int> &x){
if(s==e){ arr[now] = x; return;}
int m = s+e>>1;
if(f<=m) update(now*2,s,m,f,x);
else update(now*2+1,m+1,e,f,x);
arr[now] = min(arr[now*2],arr[now*2+1]);
}
pair<int,int> query(int now,int s, int e, int &_l, int &_r){
if(_l<=s && e<=_r) return arr[now];
if(s>_r || e<_l) return {1e9,1e9};
int m = s+e>>1;
return min(query(now*2,s,m,_l,_r), query(now*2+1,m+1,e,_l,_r));
}
} segu[2001], segd[2001];
void dnc(int row, int ud, int s, int e, int prev){
if(s>e) return;
pair<int,int> tmp;
if(ud == 1) tmp = segd[row].query(1,1,N,s,e);
else tmp = segu[row].query(1,1,N,s,e);
int x=tmp.fs, m = tmp.se;
if(x>prev) {
if (ud == 1 && segu[row].query(1,1,N,s,e).fs==1) rect.push_back({row, row + x - 1,s,e,sz(rect),0});
else if( ud == 0 && segd[row].query(1,1,N,s,e).fs==1)rect.push_back({row - x + 1, row,s,e,sz(rect),0});
}
dnc(row,ud,s,m-1,x);
dnc(row,ud,m+1,e,x);
}
int area(int rs, int re, int cs,int ce){
return (re-rs+1)*(ce-cs+1);
}
int biggest_stadium(int _N, std::vector<std::vector<int>> F)
{
N=_N;
forf(i,0,N+1) forf(j,0,N+1) arr[i][j] = 1;
forf(i,1,N) forf(j,1,N) arr[i][j] = F[i-1][j-1];
forf(i,1,N) forf(j,1,N){
if(arr[i][j] == 1) u[i][j] = 0;
else u[i][j] = u[i-1][j]+1;
}
forb(i,N,1) forb(j,N,1){
if(arr[i][j] == 1) d[i][j] = 0;
else d[i][j] = d[i+1][j]+1;
if(arr[i][j] != arr[i][j+1]) R[i][j] = 1;
else R[i][j] = R[i][j+1]+1;
}
forf(i,1,N){
forf(j,1,N) segu[i].update(1,1,N,j,{u[i][j],j});
forf(j,1,N) segd[i].update(1,1,N,j,{d[i][j],j});
}
forf(i,1,N){
dnc(i,0,1,N,0);
dnc(i,1,1,N,0);
}
assert(sz(rect) < 4000000);
sort(all(rect)); comp(rect);
forf(i,0,sz(rect)-1) rect[i].id = i;
int ans = 0;
for(auto &[rs,re,cs,ce,id,dp] : rect){
dp = max(dp, area(rs,re,cs,ce));
ans = max(ans,dp);
if(re<N) {
int nowc = cs;
while (nowc <= ce) {
int nxtc = nowc + R[re + 1][nowc];
if (arr[re + 1][nowc] == 0) {
int nce = min(nxtc - 1, ce);
int nre = re+1 + segd[re+1].query(1,1,N,nowc,nce).fs-1;
int nrs = re+1 - segu[re+1].query(1,1,N,nowc,nce).fs+1;
int ind = lower_bound(all(rect),Rect{nrs, nre ,nowc, nce,-1,0})-rect.begin();
rect[ind].dp = max(rect[ind].dp, dp +
area(rect[ind].rs, rect[ind].re, rect[ind].cs, rect[ind].ce) -
area(rs, re, rect[ind].cs, rect[ind].ce));
}
nowc = nxtc;
}
}
if(rs > 1) {
int nowc = cs;
while (nowc <= ce) {
int nxtc = nowc + R[rs - 1][nowc];
if (arr[rs - 1][nowc] == 0) {
int nce = min(nxtc - 1, ce);
int nrs = rs-1 - segu[rs-1].query(1,1,N,nowc,nce).fs+1;
int nre = rs-1 + segd[rs-1].query(1,1,N,nowc,nce).fs-1;
int ind = lower_bound(all(rect),Rect{nrs, nre, nowc, nce,-1,0})-rect.begin();
rect[ind].dp = max(rect[ind].dp, dp +
area(rect[ind].rs, rect[ind].re, rect[ind].cs, rect[ind].ce) -
area(rs, re, rect[ind].cs, rect[ind].ce));
}
nowc = nxtc;
}
}
}
return ans;
}
Compilation message
soccer.cpp: In member function 'void Seg::update(int, int, int, int&, std::pair<int, int>&)':
soccer.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int m = s+e>>1;
| ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int&, int&)':
soccer.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int m = s+e>>1;
| ~^~
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:87:55: error: cannot bind non-const lvalue reference of type 'std::pair<int, int>&' to an rvalue of type 'std::pair<int, int>'
87 | forf(j,1,N) segu[i].update(1,1,N,j,{u[i][j],j});
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from soccer.h:1,
from soccer.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:352:12: note: after user-defined conversion: 'constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = int&; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = int; _T2 = int]'
352 | constexpr pair(_U1&& __x, _U2&& __y)
| ^~~~
soccer.cpp:36:63: note: initializing argument 5 of 'void Seg::update(int, int, int, int&, std::pair<int, int>&)'
36 | void update(int now, int s, int e, int &f, pair<int,int> &x){
| ~~~~~~~~~~~~~~~^
soccer.cpp:88:55: error: cannot bind non-const lvalue reference of type 'std::pair<int, int>&' to an rvalue of type 'std::pair<int, int>'
88 | forf(j,1,N) segd[i].update(1,1,N,j,{d[i][j],j});
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from soccer.h:1,
from soccer.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:352:12: note: after user-defined conversion: 'constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = int&; _U2 = int&; typename std::enable_if<(std::_PCC<true, _T1, _T2>::_MoveConstructiblePair<_U1, _U2>() && std::_PCC<true, _T1, _T2>::_ImplicitlyMoveConvertiblePair<_U1, _U2>()), bool>::type <anonymous> = true; _T1 = int; _T2 = int]'
352 | constexpr pair(_U1&& __x, _U2&& __y)
| ^~~~
soccer.cpp:36:63: note: initializing argument 5 of 'void Seg::update(int, int, int, int&, std::pair<int, int>&)'
36 | void update(int now, int s, int e, int &f, pair<int,int> &x){
| ~~~~~~~~~~~~~~~^
