| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1113713 | lighton | Soccer Stadium (IOI23_soccer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}