Submission #1211399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211399		user736482	Soccer Stadium (IOI23_soccer)	C++20	70 / 100	4633 ms	1034052 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.ff.ff,a.ff.ss);
    swap(a.ss.ff,a.ss.ss);
    //a.ff.ff=n-a.ff.ff+1;
    //a.ff.ss=n-a.ff.ss+1;
    a.ss.ff=n-a.ss.ff+1;
    a.ss.ss=n-a.ss.ss+1;
    return toint(a);
}
void wyp(ll x){
    auto a= fromint(x);
    cout<<a.ff.ff<<" "<<a.ff.ss<<" "<<a.ss.ff<<" "<<a.ss.ss<<"    ";
}

pair<map<ll,vector<ll>>,vector<ll>>pomf2(int n,vector<vector<int>>f){
    map<ll,vector<ll>>mp;
    vector<ll>v;
    ll mx[n+7][n+7];
    ll nxt[n+7][n+7][10];
    for(ll i=1;i<=n;i++){mx[0][i]=0;nxt[n+1][i][0]=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++)nxt[n+1][i][0]=n+1;
    for(ll i=n;i>=1;i--){
        nxt[i][n+1][0]=n+1;
        for(ll j=n;j>=1;j--){
            nxt[i][j][0]=nxt[i+1][j][0];
            if(f[i-1][j-1])nxt[i][j][0]=i;
            
        }
        for(ll j=1;j<10;j++){
            for(ll k=0;k+(1<<j)-1<=n+1;k++)nxt[i][k][j]=min(nxt[i][k][j-1],nxt[i][k+(1<<(j))-1][j-1]);
        }
    }
    for(ll i=0;i<=n+1;i++){
        for(ll j=0;j<=n+1;j++){
            //cout<<nxt[i][j][0]<<" "<<mx[i][j]<<"   ";
        }
        //cout<<"\n";
    }
   // cout<<"\n\n";
    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;
        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;
        }
        for(ll i=1;i<=n;i++){
          //  cout<<lwp[i]<<" "<<pwp[i]<< "   ";
    
        }
       // cout<<"\n";
        stack<pair<ll,ll>>st;
        st.push({10000,0});
        //return {mp,v};
        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;
            //cout<<pw[j]<<"aa   ";
            ll lx=lw[j]+1;
            ll px=pw[j]-1;
            ll ly=mx[i][j]+1;
            ll py=i;
            //cout<<lx<<" "<<px<<" "<<ly<<" "<<py<<"\n\n";
            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[i][lx][lg],nxt[i][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;
            }
            //cout<<lx2<<" "<<px2<<" "<<ly2<<" "<<py2<<"\n\n\n";
            mp[toint({{lx2,px2},{ly2,py}})].pb(toint({{lx,px},{ly,py2}}));
        }
        
    }
    
    return {mp,v};
}

int biggest_stadium2(int n,vector<vector<int>>f){
    ll ans=0;
    for(auto i :f){
      //  for(auto j : i)cout<<j<<" ";
     //   cout<<"\n";
    }
  //  cout<<"\n";
    auto pom=pomf2(n,f);
    //return 0;
    vector<ll>states=pom.ss;
  //  cout<<"\n\n\n";
    map<ll,vector<ll>>przej=pom.ff;
  //  for(ll i : states){wyp(i);/*cout<<":   ";for(ll j : pom.ff[i])wyp(j);*/cout<<"\n";}//return 0;
    
    for(auto it : przej){
        
       // wyp(it.ff);
      //  cout<<":  ";
       // for(ll i : it.ss)wyp(i);
      //  cout<<"\n";
    }
    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]);
    }//return 0;
    for(auto i :f){
    //    for(auto j : i)cout<<j<<" ";
    //    cout<<"\n";
    }
  //  cout<<"\n";
    auto pom2=pomf2(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));
    }
    //cout<<"\n\n\n";
    for(ll i : states){//wyp(i);/*cout<<":   ";for(ll j : pom.ff[i])wyp(j);*/cout<<"\n";
        
    }//return 0;
    
    for(auto it : przej){
        
        //wyp(it.ff);
        //cout<<":  ";
        //for(ll i : it.ss)wyp(i);
        //cout<<"\n";
    }
    sort(states.begin(),states.end(),[](const ll & a,const ll & b){
        auto poma=fromint(a);
        auto pomb=fromint(b);
        return poma.ff.ss-poma.ff.ff>pomb.ff.ss-pomb.ff.ff;
    });
    for(ll i : states){
        //wyp(i);
        auto pomi=fromint(i);
        bst[i]=max(bst[i],(pomi.ff.ss-pomi.ff.ff+1)*(pomi.ss.ss-pomi.ss.ff+1));
        //cout<<bst[i]<<"\n";
        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;
    
}

pair<map<ll,vector<ll>>,vector<ll>>pomf(int n,vector<vector<int>>f){
    map<ll,vector<ll>>mp;
    vector<ll>v;
    ll mx[n+7][n+7];
    ll nxt[n+7][n+7][11];
    for(ll i=1;i<=n;i++){mx[0][i]=0;nxt[n+1][i][0]=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++)nxt[n+1][i][0]=n+1;
    for(ll i=n;i>=1;i--){
        nxt[i][n+1][0]=n+1;
        for(ll j=n;j>=1;j--){
            nxt[i][j][0]=nxt[i+1][j][0];
            if(f[i-1][j-1])nxt[i][j][0]=i;
            
        }
        for(ll j=1;j<11;j++){
            for(ll k=0;k+(1<<j)-1<=n+1;k++)nxt[i][k][j]=min(nxt[i][k][j-1],nxt[i][k+(1<<(j-1))][j-1]);
        }
    }
    for(ll i=0;i<=n+1;i++){
        for(ll j=0;j<=n+1;j++){
            //cout<<nxt[i][j][0]<<" "<<mx[i][j]<<"   ";
        }
        //cout<<"\n";
    }
   // cout<<"\n\n";
    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;
        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;
        }
        for(ll i=1;i<=n;i++){
          //  cout<<lwp[i]<<" "<<pwp[i]<< "   ";
    
        }
       // cout<<"\n";
        stack<pair<ll,ll>>st;
        st.push({10000,0});
        //return {mp,v};
        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;
            //cout<<pw[j]<<"aa   ";
            ll lx=lw[j]+1;
            ll px=pw[j]-1;
            ll ly=mx[i][j]+1;
            ll py=i;
            //cout<<lx<<" "<<px<<" "<<ly<<" "<<py<<"\n\n";
            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);
            //cout<<lg<<" ";
            //for(ll k=lx;k<=px;k++)cout<<nxt[i][k][1]<<" ";
            //cout<<"     ";
            ll py2=min(nxt[i][lx][lg],nxt[i][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;
            }
            //cout<<lx2<<" "<<px2<<" "<<ly2<<" "<<py2<<"\n\n\n";
            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;
    for(auto i :f){
      //  for(auto j : i)cout<<j<<" ";
     //   cout<<"\n";
    }
  //  cout<<"\n";
    auto pom=pomf(n,f);
    //cout<<"\n\n\n\n";
    //return 0;
    vector<ll>states=pom.ss;
  //  cout<<"\n\n\n";
    map<ll,vector<ll>>przej=pom.ff;
    //for(ll i : states){wyp(i);/*cout<<":   ";for(ll j : pom.ff[i])wyp(j);*/cout<<"\n";}//return 0;
    
    for(auto it : przej){
        
        //wyp(it.ff);
        //cout<<":  ";
        //for(ll i : it.ss)wyp(i);
        //cout<<"\n";
    }
    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]);
    }//return 0;
    for(auto i :f){
    //    for(auto j : i)cout<<j<<" ";
    //    cout<<"\n";
    }
  //  cout<<"\n";
    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));
    }
    //cout<<"\n\n\n";
    for(ll i : states){//wyp(i);/*cout<<":   ";for(ll j : pom.ff[i])wyp(j);*/cout<<"\n";
        
    }//return 0;
    
    for(auto it : przej){
        
        //wyp(it.ff);
        //cout<<":  ";
        //for(ll i : it.ss)wyp(i);
        //cout<<"\n";
    }
    sort(states.begin(),states.end(),[](const ll & a,const ll & b){
        auto poma=fromint(a);
        auto pomb=fromint(b);
        return poma.ff.ss-poma.ff.ff>pomb.ff.ss-pomb.ff.ff;
    });
    for(ll i : states){
        //wyp(i);
        auto pomi=fromint(i);
        bst[i]=max(bst[i],(pomi.ff.ss-pomi.ff.ff+1)*(pomi.ss.ss-pomi.ss.ff+1));
        //cout<<bst[i]<<"\n";
        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