Submission #1113715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113715		lighton	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	4400 ms	425536 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];
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];
struct Seg2{
    int arr[8001];
    void update(int now, int s, int e, int f, 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]);
    }
    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;
        int m = s+e>>1;
        return min(query(now*2,s,m,_l,_r),  query(now*2+1,m+1,e,_l,_r));
    }
} segu2[2001], segd2[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 && segu2[row].query(1,1,N,s,e)==1) rect.push_back({row, row + x - 1,s,e,sz(rect),0});
        else if( ud == 0 && segd2[row].query(1,1,N,s,e)==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(j,1,N) segu2[i].update(1,1,N,j,u[i][j]);
        forf(j,1,N) segd2[i].update(1,1,N,j,d[i][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 + segd2[re+1].query(1,1,N,nowc,nce)-1;
                    int nrs = re+1 - segu2[re+1].query(1,1,N,nowc,nce)+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 - segu2[rs-1].query(1,1,N,nowc,nce)+1;
                    int nre = rs-1 + segd2[rs-1].query(1,1,N,nowc,nce)-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 (stderr)

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 member function 'void Seg2::update(int, int, int, int, int)':
soccer.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'int Seg2::query(int, int, int, int, int)':
soccer.cpp:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         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: 16 / 16
• Subtask 6: 30 / 30