#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];
struct Rect{
int id,rs,re,cs,ce,dp;
bool operator<(const Rect &r) const{
if(ce-cs == r.ce-r.cs){
if(re-rs == r.re-rs) return id<r.id;
return re-rs < r.re-rs;
}
return ce-cs > r.ce-r.cs;
}
};
vector<Rect> rect;
map<array<int,4>, int> irect;
struct Seg{
pair<int,int> arr[100001];
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));
}
} seg;
void dnc(int row, int ud, int s, int e){
if(s>e) return;
auto [x,m] = seg.query(1,1,N,s,e);
if(x>0) {
if (ud == 1) rect.push_back({sz(rect),row, row + x - 1,s,e,0});
else rect.push_back({sz(rect),row - x + 1, row,s,e,0});
}
dnc(row,ud,s,m-1);
dnc(row,ud,m+1,e);
}
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) seg.update(1,1,N,j,{u[i][j],j});
dnc(i,0,1,N);
forf(j,1,N) seg.update(1,1,N,j,{d[i][j],j});
dnc(i,1,1,N);
}
sort(all(rect));
forf(i,0,sz(rect)-1) irect[{rect[i].rs,rect[i].re,rect[i].cs,rect[i].ce}] = i;
int ans = 0;
for(auto &[id, rs,re,cs,ce,dp] : rect){
dp = max(dp, area(rs,re,cs,ce));
ans = max(ans,dp);
int nowc = cs;
if(re<N) {
while (nowc <= ce) {
int nxtc = nowc + R[re + 1][nowc];
if (arr[re + 1][nowc] == 0) {
if (irect.find({rs, re + 1, nowc, min(nxtc - 1, ce)}) != irect.end()) {
int ind = irect[{rs, re + 1, nowc, min(nxtc - 1, ce)}];
assert(ind > id);
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) {
nowc = cs;
while (nowc <= ce) {
int nxtc = nowc + R[rs - 1][nowc];
if (arr[rs - 1][nowc] == 0) {
if (irect.find({rs - 1, re, nowc, min(nxtc - 1, ce)}) != irect.end()) {
int ind = irect[{rs - 1, re, nowc, min(nxtc - 1, ce)}];assert(ind > id);
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:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int m = s+e>>1;
| ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int, int)':
soccer.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int m = s+e>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
13136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
8952 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
8952 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
13136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
13136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
13136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
13136 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
