Submission #1113709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113709		lighton	Soccer Stadium (IOI23_soccer)	C++17	54 / 100	4566 ms	427020 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 rs,re,cs,ce,id,dp;
    bool operator<(const Rect &r) const{
        return array<int,5>{cs-ce, re-rs, rs, cs, id} < array<int,5>{r.cs-r.ce, r.re-r.rs, r.rs, 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){
    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>0) {
        if (ud == 1) rect.push_back({row, row + x - 1,s,e,sz(rect),0});
        else rect.push_back({row - x + 1, row,s,e,sz(rect),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) segu[i].update(1,1,N,j,{u[i][j],j});
        dnc(i,0,1,N);
        forf(j,1,N) segd[i].update(1,1,N,j,{d[i][j],j});
        dnc(i,1,1,N);
    }

    sort(all(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(segu[rs].query(1,1,N,cs,ce).fs != 1 || segd[re].query(1,1,N,cs,ce).fs != 1) continue;

        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();

                    if(ind < sz(rect) && rect[ind] == Rect{nrs, nre, nowc, nce}) {
                        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();
                    if(ind < sz(rect) && rect[ind] == Rect{nrs, nre, nowc, nce}) {
                        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:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int, int)':
soccer.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m = s+e>>1;
      |                 ~^~

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