Submission #1211429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211429		user736482	Soccer Stadium (IOI23_soccer)	C++20	100 / 100	3755 ms	640900 KiB

soccer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll toint(pair<pair<ll,ll>,pair<ll,ll>>a){
    return ((a.ff.ff*2007LL+a.ff.ss)*2007LL+a.ss.ff)*2007LL+a.ss.ss;
}
pair<pair<ll,ll>,pair<ll,ll>>fromint(ll x){
    return {{(x/(2007LL*2007LL*2007LL))%2007,(x/(2007LL*2007LL))%2007},{(x/2007)%2007,x%2007}};
}
ll inv(ll aa,ll n){
    auto a=fromint(aa);
    swap(a.ss.ff,a.ss.ss);
    a.ss.ff=n-a.ss.ff+1;
    a.ss.ss=n-a.ss.ss+1;
    return toint(a);
}
pair<vector<pair<ll,ll>>,vector<ll>>pomf(int n,vector<vector<int>>f){
    vector<pair<ll,ll>>mp;
    vector<ll>v;
    int mx[n+7][n+7];
    int  nxt2[n+7][n+7];
    for(ll i=1;i<=n;i++){mx[0][i]=0;nxt2[n+1][i]=n+1;}
    for(ll i=1;i<=n;i++){
        mx[i][0]=10000;
        mx[i][n+1]=10000;
        for(ll j=1;j<=n;j++){
            mx[i][j]=mx[i-1][j];
            if(f[i-1][j-1])mx[i][j]=i;
        }
        mx[n+1][i]=n+1;
    }
    for(ll i=0;i<=n+1;i++)nxt2[n+1][i]=n+1;
    for(ll i=n;i>=1;i--){
        nxt2[i][n+1]=n+1;
        for(ll j=n;j>=1;j--){
            nxt2[i][j]=nxt2[i+1][j];
            if(f[i-1][j-1])nxt2[i][j]=i;
        }
        
    }
    for(ll i=1;i<=n;i++){
        ll lw[n+7],pw[n+7],lwp[n+7],pwp[n+7],pomlw[n+7];
        lwp[0]=0;
        pwp[n+1]=n+1;
        ll nxt[n+7][11];
        for(ll j=0;j<=n+1;j++)nxt[j][0]=nxt2[i][j];
        for(ll j=1;j<11;j++){
            for(ll k=0;k+(1<<j)-1<=n+1;k++)nxt[k][j]=min(nxt[k][j-1],nxt[k+(1<<(j-1))][j-1]);
        }
        for(ll j=1;j<=n;j++){
            lwp[j]=lwp[j-1];
            if(mx[i+1][j]==i+1)lwp[j]=j;
        }
        for(ll j=n;j>=1;j--){
            pwp[j]=pwp[j+1];
            if(mx[i+1][j]==i+1)pwp[j]=j;
        }
        stack<pair<ll,ll>>st;
        st.push({10000,0});
        for(ll j=1;j<=n;j++){
            while(mx[i][j]>st.top().ff)st.pop();
            pomlw[j]=st.top().ss;
            st.push({mx[i][j],j});
        }
        while(st.size())st.pop();
        st.push({10000,0});
        for(ll j=1;j<=n;j++){
            while(mx[i][j]>=st.top().ff)st.pop();
            lw[j]=st.top().ss;
            st.push({mx[i][j],j});
        }
        while(st.size())st.pop();
        st.push({10000,n+1});
        for(ll j=n;j>=1;j--){
            while(mx[i][j]>=st.top().ff)st.pop();
            pw[j]=st.top().ss;
            st.push({mx[i][j],j});
        }
        lw[0]=0;
        lw[n+1]=n+1;
        pw[0]=0;
        pw[n+1]=n+1;
        for(ll j=1;j<=n;j++){
            if(mx[i][pomlw[j]]==mx[i][j])continue;
            ll lx=lw[j]+1;
            ll px=pw[j]-1;
            ll ly=mx[i][j]+1;
            ll py=i;
            if((lwp[j]>=lx || pwp[j]<=px) && lx<=px & ly<=py){
                v.pb(toint({{lx,px},{ly,py}}));
            }
            if(lx==1 && px==n)continue;
            ll lg=log2(px-lx+1);
            ll py2=min(nxt[lx][lg],nxt[px-(1<<lg)+1][lg])-1;
            ll ly2=min(mx[i][lx-1],mx[i][px+1])+1;
            ll lx2,px2;
            if(ly2==mx[i][lx-1]+1){
                lx2=lw[lx-1]+1;
                px2=pw[lx-1]-1;
            }
            else{
                lx2=lw[px+1]+1;
                px2=pw[px+1]-1;
            }
            mp.pb({toint({{lx2,px2},{ly2,py}}),toint({{lx,px},{ly,py2}})});
        }
    }
    return {mp,v};
}
int biggest_stadium(int n,vector<vector<int>>f){
    ll ans=0;
    auto pom=pomf(n,f);
    vector<ll>states=pom.ss;
    vector<pair<ll,ll>>przej=pom.ff;
    unordered_map<ll,ll>bst;
    for(ll i=0;i<n/2;i++){
        for(ll j=0;j<n;j++)swap(f[i][j],f[n-i-1][j]);
    }
    auto pom2=pomf(n,f);
    for(ll i : pom2.ss)states.pb(inv(i,n));
        for(pair<ll,ll> i : pom2.ff)przej.pb({inv(i.ff,n),inv(i.ss,n)});
   vector<ll>pm[2007];
   vector<pair<ll,ll>>pm2[2007];
   for(ll a : states){
       auto poma=fromint(a);
       pm[poma.ff.ss-poma.ff.ff].pb(a);
   }
   for(pair<ll,ll>a : przej){
       auto poma=fromint(a.ff);
       auto pomb=fromint(a.ss);
       pm2[poma.ff.ss-poma.ff.ff].pb(a);
   }
   states.clear();
   przej.clear();
   for(ll i=2006;i>=0;i--){
       for(ll j : pm[i]){
            auto pomi=fromint(j);
            bst[j]=max(bst[j],(pomi.ff.ss-pomi.ff.ff+1)*(pomi.ss.ss-pomi.ss.ff+1));
            ans=max(ans,bst[j]);
       }
       for(auto j : pm2[i]){
           auto pomi=fromint(j.ff);
           auto pomj=fromint(j.ss);
           bst[j.ss]=max(bst[j.ss],bst[j.ff]+(pomj.ss.ss-pomj.ss.ff-pomi.ss.ss+pomi.ss.ff)*(pomj.ff.ss-pomj.ff.ff+1));
       }
   }
   /* for(ll i : states){
        auto pomi=fromint(i);
        bst[i]=max(bst[i],(pomi.ff.ss-pomi.ff.ff+1)*(pomi.ss.ss-pomi.ss.ff+1));
        ans=max(ans,bst[i]);
        for(ll j : przej[i]){
            auto pomj=fromint(j);
            bst[j]=max(bst[j],bst[i]+(pomj.ss.ss-pomj.ss.ff-pomi.ss.ss+pomi.ss.ff)*(pomj.ff.ss-pomj.ff.ff+1));
        }
   }*/
    return ans;
}

• 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