제출 #1211427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211427		user736482	축구 경기장 (IOI23_soccer)	C++20	70 / 100	4534 ms	778640 KiB

soccer

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#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<unordered_map<ll,vector<ll>>,vector<ll>>pomf(int n,vector<vector<int>>f){
    unordered_map<ll,vector<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[toint({{lx2,px2},{ly2,py}})].pb(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;
    unordered_map<ll,vector<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(auto it : pom2.ff){
        for(ll i : (it).ss)przej[inv((it).ff,n)].pb(inv(i,n));
    }
   vector<ll>pm[2007];
   for(ll a : states){
       auto poma=fromint(a);
       pm[poma.ff.ss-poma.ff.ff].pb(a);
   }
   states.clear();
   for(ll i=2006;i>=0;i--){
       for(ll j : pm[i])states.pb(j);
   }
    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: 0 / 30