Submission #1113683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113683		lighton	Soccer Stadium (IOI23_soccer)	C++17	8 / 100	4612 ms	705916 KiB

soccer

#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-r.rs) return id<r.id;
            return re-rs < r.re-r.rs;
        }
        return ce-cs > r.ce-r.cs;
    }
    bool operator==(const Rect &r) const{
        if(rs!=r.rs) return false;
        if(re!=r.re) return false;
        if(cs!=r.cs) return false;
        if(ce!=r.ce) return false;
        return true;
    }
};
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)); comp(rect);
    forf(i,0,sz(rect)-1) rect[i].id = i+1;
    forf(i,0,sz(rect)-1) irect[{rect[i].rs,rect[i].re,rect[i].cs,rect[i].ce}] = i+1;
    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)}]-1;
                        assert(ind > id-1);
                        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)}]-1;assert(ind > id-1);
                        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 (stderr)

soccer.cpp: In member function 'void Seg::update(int, int, int, int, std::pair<int, int>)':
soccer.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int, int)':
soccer.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int m = s+e>>1;
      |                 ~^~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30