제출 #1188921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1188921		user736482	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	3611 ms	65388 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
//#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 INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,r,c,t,n,m,l,q,k,ak,ans,s,h,w;
ll mp[300007];
vector<ll>mog[5][5];
vector<vector<ll>>in,pref[81];
vector<pair<ll,ll>>sas={{0,1},{1,0},{0,-1},{-1,0}};
ll czy(ll i,ll j,ll k){
    ll l=max(-(k%3),-j);k/=3;
    ll p=min((k%3),w-j-1);k/=3;
    ll g=max(-(k%3),-i);k/=3;
    ll d=min(k%3,h-i-1);
    ll ile=0;
    bool czy=0;
    for(auto x : sas){
        if(x.ff>=g && x.ff<=d && x.ss>=l && x.ss<=p){
            if(in[x.ff+i][x.ss+j]<in[i][j])czy=1;
            ll mx=-1;
            for(auto o : sas ){
                pair<ll,ll> y={x.ff+o.ff,x.ss+o.ss};  
                if(y.ff>=g && y.ff<=d && y.ss>=l && y.ss<=p){
                    if(in[y.ff+i][y.ss+j]<in[x.ff+i][x.ss+j])
                    mx=max(mx,in[y.ff+i][y.ss+j]);
                }
            }
            if(mx==in[i][j])ile++;
        }
    }
    return (!czy)+(ile!=1);
}
vector<ll>f(ll i1,ll i2,ll j1,ll j2,ll pom1,ll pom2,ll pom3,ll pom4){
    vector<ll> cnt;
    for(ll i=0;i<81;i++){
        ll k=i;
        ll d=(k%3);k/=3;
        ll g=(k%3);k/=3;
        ll p=(k%3);k/=3;
        ll l=(k%3);
        ll pf=pom2,lf=pom1,df=pom4,gf=pom3;
        if(p==0){
            lf=max(i1,lf);
            pf=min(pf,i1);
        }
        else if(p==1){
            lf=max(i1+1,lf);
            pf=min(pf,i1+1);
        }
        else lf=max(i1+2,lf);
        if(l==0){
            lf=max(i2,lf);
            pf=min(pf,i2);
        }
        else if(l==1){
            lf=max(i2-1,lf);
            pf=min(pf,i2-1);
        }
        else pf=min(i2-2,pf);
        if(d==0){
            gf=max(j1,gf);
            df=min(df,j1);
        }
        else if(d==1){
            gf=max(j1+1,gf);
            df=min(df,j1+1);
        }
        else gf=max(j1+2,gf);
        if(g==0){
            gf=max(j2,gf);
            df=min(df,j2);
        }
        else if(g==1){
            gf=max(j2-1,gf);
            df=min(df,j2-1);
        }
        else df=min(j2-2,df);
        if(lf<=pf && gf<=df){
            cnt.pb(i);
        }
    }
    return cnt;
}
ll zle(ll i1,ll i2,ll j1,ll j2,ll pom1,ll pom2,ll pom3,ll pom4){
    ll cnt=0;
    for(ll i : mog[min(i2-i1,4LL)][min(j2-j1,4LL)]){
        ll k=i;
        ll d=(k%3);k/=3;
        ll g=(k%3);k/=3;
        ll p=(k%3);k/=3;
        ll l=(k%3);
        ll pf=pom2,lf=pom1,df=pom4,gf=pom3;
        if(p==0){
            lf=max(i1,lf);
            pf=min(pf,i1);
        }
        else if(p==1){
            lf=max(i1+1,lf);
            pf=min(pf,i1+1);
        }
        else lf=max(i1+2,lf);
        if(l==0){
            lf=max(i2,lf);
            pf=min(pf,i2);
        }
        else if(l==1){
            lf=max(i2-1,lf);
            pf=min(pf,i2-1);
        }
        else pf=min(i2-2,pf);
        if(d==0){
            gf=max(j1,gf);
            df=min(df,j1);
        }
        else if(d==1){
            gf=max(j1+1,gf);
            df=min(df,j1+1);
        }
        else gf=max(j1+2,gf);
        if(g==0){
            gf=max(j2,gf);
            df=min(df,j2);
        }
        else if(g==1){
            gf=max(j2-1,gf);
            df=min(df,j2-1);
        }
        else df=min(j2-2,df);
        if(lf<=pf && gf<=df){
            cnt+=(pref[i][pf+1][df+1]-pref[i][lf][df+1]-pref[i][pf+1][gf]+pref[i][lf][gf]);
        }
    }
    return cnt;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>h>>w;
    if(h>w){
        for(ll i=0;i<w;i++)in.pb({});
        for(ll i=0;i<h;i++){
            for(ll j=0;j<w;j++){
                cin>>a;
                in[j].pb(a);
            }
        }
        swap(h,w);
    }
    else{
        for(ll i=0;i<h;i++){
            in.pb({});
            for(ll j=0;j<w;j++){
                cin>>a;
                in.back().pb(a);
            }
        }
    }
    for(ll i=0;i<81;i++){
        pref[i].pb({});
        for(ll j=0;j<w;j++){
            pref[i].back().pb(0);
        }
        for(ll j=0;j<h;j++)pref[i].pb({0});
    }
    for(ll i=0;i<81;i++){
        for(ll j=1;j<=h;j++){
            for(ll k=1;k<=w;k++){
                pref[i][j].pb(pref[i][j-1][k]+pref[i][j][k-1]-pref[i][j-1][k-1]+czy(j-1,k-1,i));
            }
        }
    }
    for(ll i=0;i<5;i++){
        for(ll j=0;j<5;j++){
            mog[i][j]=f(0,i,0,j,0,i,0,j);
        }
    }
    for(ll i=0;i<h;i++){
        for(ll j=i;j<h;j++){
            for(ll k=0;k<w;k++){
                for(ll p=k;p<min(k+3,w);p++){
                    if(zle(i,j,k,p,i,j,k,p)==2)ans++;
                }
            }
            vector<ll>v;
            for(ll k=0;k<w;k++){
                v.pb(zle(i,j,k,w+2,i,j,k,w-1));
                mp[100000+v.back()]++;
                if(k+3<w){
                    ans+=mp[100000+2-(zle(i,j,-3,k+3,i,j,k+2,k+3)-zle(i,j,k,w+2,i,j,k+2,w-1))];
                }
            }
            for(ll k : v)mp[100000+k]--;
        }
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20