Submission #858581

#	Time	Username	Problem	Language	Result	Execution time	Memory
858581		arnold518	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	2040 ms	397552 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef array<array<array<array<int, 3>, 3>, 3>, 3> pi4;

const int MAXN = 5e4;

int N, M;
vector<vector<int>> A;
vector<vector<pi4>> P1, P2, S1, S2, H1, H2, V1, V2;
vector<int> B11, B12, B21, B22;

inline bool isin(int i, int j, int li, int ri, int lj, int rj)
{
    return li<=i && i<=ri && lj<=j && j<=rj;
}

inline int getout(int i, int j, int li, int ri, int lj, int rj)
{
    if(!isin(i, j, li, ri, lj, rj)) return 5;
    pii ret={0, 4};
    if(isin(i-1, j, li, ri, lj, rj) && A[i-1][j]<A[i][j]) ret=max(ret, pii(A[i-1][j], 0));
    if(isin(i+1, j, li, ri, lj, rj) && A[i+1][j]<A[i][j]) ret=max(ret, pii(A[i+1][j], 1));
    if(isin(i, j-1, li, ri, lj, rj) && A[i][j-1]<A[i][j]) ret=max(ret, pii(A[i][j-1], 2));
    if(isin(i, j+1, li, ri, lj, rj) && A[i][j+1]<A[i][j]) ret=max(ret, pii(A[i][j+1], 3));
    return ret.second;
}

inline int query(vector<vector<pi4>> &S, int pi, int qi, int pj, int qj, int li, int ri, int lj, int rj)
{
    return S[ri][rj][pi][qi][pj][qj]-S[li-1][rj][pi][qi][pj][qj]-S[ri][lj-1][pi][qi][pj][qj]+S[li-1][lj-1][pi][qi][pj][qj];
}

int naive(int li, int ri, int lj, int rj)
{
    vector<pair<int, pii>> V;
    for(int i=li; i<=ri; i++) for(int j=lj; j<=rj; j++) V.push_back({A[i][j], {i, j}});
    sort(V.begin(), V.end());
    for(int i=1; i<V.size(); i++) if(abs(V[i].second.first-V[i-1].second.first)+abs(V[i].second.second-V[i-1].second.second)!=1) return false;
    return true;
}

ll ans=0;

void solve()
{
    map<pii, int> MM;
    for(int i=4; i<=M; i++)
    {
        MM[{B11[i-3], B21[i-3]}]++;
        int t1=1-B12[i], t2=1-B22[i];
        ans+=MM[{t1, t2}];
        //printf("%d : %d\n", i, MM[{t1, t2}]);
    }
}

int main()
{
    scanf("%d%d", &N, &M);
    if(N<=M)
    {
        A=vector<vector<int>>(N+2, vector<int>(M+2));
        for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);
    }
    else
    {
        swap(N, M);
        A=vector<vector<int>>(N+2, vector<int>(M+2));
        for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) scanf("%d", &A[j][i]);
    }
    P1=P2=S1=S2=H1=H2=V1=V2=vector<vector<pi4>>(N+2, vector<pi4>(M+2));

    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            for(int pi=0; pi<3; pi++) for(int qi=0; qi<3; qi++)
            {
                for(int pj=0; pj<3; pj++) for(int qj=0; qj<3; qj++)
                {
                    int li=i-pi, ri=i+qi, lj=j-pj, rj=j+qj;
                    if(!(1<=li && ri<=N && 1<=lj && rj<=M)) continue;

                    if(getout(i, j, li, ri, lj, rj)>=4) P1[i][j][pi][qi][pj][qj]=1;

                    int cnt=0;
                    if(getout(i-1, j, li, ri, lj, rj)==1) cnt++;
                    if(getout(i+1, j, li, ri, lj, rj)==0) cnt++;
                    if(getout(i, j-1, li, ri, lj, rj)==3) cnt++;
                    if(getout(i, j+1, li, ri, lj, rj)==2) cnt++;
                    if(cnt!=1) P2[i][j][pi][qi][pj][qj]=1;
                }
            }
        }
    }
    
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=M; j++)
        {
            for(int pi=0; pi<3; pi++) for(int qi=0; qi<3; qi++)
            {
                for(int pj=0; pj<3; pj++) for(int qj=0; qj<3; qj++)
                {
                    S1[i][j][pi][qi][pj][qj]=P1[i][j][pi][qi][pj][qj]+S1[i-1][j][pi][qi][pj][qj]+S1[i][j-1][pi][qi][pj][qj]-S1[i-1][j-1][pi][qi][pj][qj];
                    S2[i][j][pi][qi][pj][qj]=P2[i][j][pi][qi][pj][qj]+S2[i-1][j][pi][qi][pj][qj]+S2[i][j-1][pi][qi][pj][qj]-S2[i-1][j-1][pi][qi][pj][qj];
                    H1[i][j][pi][qi][pj][qj]=P1[i][j][pi][qi][pj][qj]+H1[i][j-1][pi][qi][pj][qj];
                    H2[i][j][pi][qi][pj][qj]=P2[i][j][pi][qi][pj][qj]+H2[i][j-1][pi][qi][pj][qj];
                    V1[i][j][pi][qi][pj][qj]=P1[i][j][pi][qi][pj][qj]+V1[i-1][j][pi][qi][pj][qj];
                    V2[i][j][pi][qi][pj][qj]=P2[i][j][pi][qi][pj][qj]+V2[i-1][j][pi][qi][pj][qj];
                }
            }
        }
    }

    for(int i=1; i<=N; i++) for(int j=i; j<=N; j++)
    {
        B11=B12=B21=B22=vector<int>(M+2);
        if(i==j)
        {

            ans+=M+M-1;
            for(int k=3; k<=M; k++) if((A[i][k-2]>A[i][k-1] && A[i][k-1]>A[i][k]) || (A[i][k-2]<A[i][k-1] && A[i][k-1]<A[i][k])) ans++;

            for(int k=1; k<=M; k++)
            {
                if(k+1<=M) B11[k]+=P1[i][k][0][0][0][2]+P1[i][k+1][0][0][1][2]-H1[i][k+1][0][0][2][2];
                if(k-2>=0) B12[k]+=P1[i][k][0][0][2][0]+P1[i][k-1][0][0][2][1]+H1[i][k-2][0][0][2][2];              
                if(k+1<=M) B21[k]+=P2[i][k][0][0][0][2]+P2[i][k+1][0][0][1][2]-H2[i][k+1][0][0][2][2];
                if(k-2>=0) B22[k]+=P2[i][k][0][0][2][0]+P2[i][k-1][0][0][2][1]+H2[i][k-2][0][0][2][2];
            }
            //printf("!%d\n", i);
            //for(int k=1; k<=M; k++) printf("%d : %d %d %d %d\n", k, B11[k], B12[k], B21[k], B22[k]);
            solve();
        }
        else if(i+1==j)
        {
            ans+=M;
            for(int k=2; k<=M; k++) ans+=naive(i, j, k-1, k);
            for(int k=3; k<=M; k++) ans+=naive(i, j, k-2, k);
            for(int k=1; k<=M; k++)
            {
                if(k+1<=M) B11[k]+=P1[i][k][0][1][0][2]+P1[i][k+1][0][1][1][2]-H1[i][k+1][0][1][2][2];
                if(k-2>=0) B12[k]+=P1[i][k][0][1][2][0]+P1[i][k-1][0][1][2][1]+H1[i][k-2][0][1][2][2];              
                if(k+1<=M) B21[k]+=P2[i][k][0][1][0][2]+P2[i][k+1][0][1][1][2]-H2[i][k+1][0][1][2][2];
                if(k-2>=0) B22[k]+=P2[i][k][0][1][2][0]+P2[i][k-1][0][1][2][1]+H2[i][k-2][0][1][2][2];

                if(k+1<=M) B11[k]+=P1[i+1][k][1][0][0][2]+P1[i+1][k+1][1][0][1][2]-H1[i+1][k+1][1][0][2][2];
                if(k-2>=0) B12[k]+=P1[i+1][k][1][0][2][0]+P1[i+1][k-1][1][0][2][1]+H1[i+1][k-2][1][0][2][2];              
                if(k+1<=M) B21[k]+=P2[i+1][k][1][0][0][2]+P2[i+1][k+1][1][0][1][2]-H2[i+1][k+1][1][0][2][2];
                if(k-2>=0) B22[k]+=P2[i+1][k][1][0][2][0]+P2[i+1][k-1][1][0][2][1]+H2[i+1][k-2][1][0][2][2];
            }
            solve();
        }
        else if(i+2==j)
        {
            for(int k=1; k<=M; k++) ans+=naive(i, j, k, k);
            for(int k=2; k<=M; k++) ans+=naive(i, j, k-1, k);
            for(int k=3; k<=M; k++) ans+=naive(i, j, k-2, k);

            for(int k=1; k<=M; k++)
            {
                if(k+1<=M) B11[k]+=P1[i][k][0][2][0][2]+P1[i][k+1][0][2][1][2]-H1[i][k+1][0][2][2][2];
                if(k-2>=0) B12[k]+=P1[i][k][0][2][2][0]+P1[i][k-1][0][2][2][1]+H1[i][k-2][0][2][2][2];              
                if(k+1<=M) B21[k]+=P2[i][k][0][2][0][2]+P2[i][k+1][0][2][1][2]-H2[i][k+1][0][2][2][2];
                if(k-2>=0) B22[k]+=P2[i][k][0][2][2][0]+P2[i][k-1][0][2][2][1]+H2[i][k-2][0][2][2][2];

                if(k+1<=M) B11[k]+=P1[i+1][k][1][1][0][2]+P1[i+1][k+1][1][1][1][2]-H1[i+1][k+1][1][1][2][2];
                if(k-2>=0) B12[k]+=P1[i+1][k][1][1][2][0]+P1[i+1][k-1][1][1][2][1]+H1[i+1][k-2][1][1][2][2];              
                if(k+1<=M) B21[k]+=P2[i+1][k][1][1][0][2]+P2[i+1][k+1][1][1][1][2]-H2[i+1][k+1][1][1][2][2];
                if(k-2>=0) B22[k]+=P2[i+1][k][1][1][2][0]+P2[i+1][k-1][1][1][2][1]+H2[i+1][k-2][1][1][2][2];

                if(k+1<=M) B11[k]+=P1[i+2][k][2][0][0][2]+P1[i+2][k+1][2][0][1][2]-H1[i+2][k+1][2][0][2][2];
                if(k-2>=0) B12[k]+=P1[i+2][k][2][0][2][0]+P1[i+2][k-1][2][0][2][1]+H1[i+2][k-2][2][0][2][2];              
                if(k+1<=M) B21[k]+=P2[i+2][k][2][0][0][2]+P2[i+2][k+1][2][0][1][2]-H2[i+2][k+1][2][0][2][2];
                if(k-2>=0) B22[k]+=P2[i+2][k][2][0][2][0]+P2[i+2][k-1][2][0][2][1]+H2[i+2][k-2][2][0][2][2];
            }
            solve();
        }
        else
        {
            for(int k=1; k<=M; k++)
            {
                int t1=0, t2=0;
                t1+=P1[i][k][0][2][0][0]+P1[i+1][k][1][2][0][0]+P1[j-1][k][2][1][0][0]+P1[j][k][2][0][0][0]+V1[j-2][k][2][2][0][0]-V1[i+1][k][2][2][0][0];
                t2+=P2[i][k][0][2][0][0]+P2[i+1][k][1][2][0][0]+P2[j-1][k][2][1][0][0]+P2[j][k][2][0][0][0]+V2[j-2][k][2][2][0][0]-V2[i+1][k][2][2][0][0];
                if(t1==1 && t2==1) ans++;
            }
            for(int k=1; k<=M-1; k++)
            {
                int t1=0, t2=0;
                t1+=P1[i][k][0][2][0][1]+P1[i+1][k][1][2][0][1]+P1[j-1][k][2][1][0][1]+P1[j][k][2][0][0][1]+V1[j-2][k][2][2][0][1]-V1[i+1][k][2][2][0][1];
                t2+=P2[i][k][0][2][0][1]+P2[i+1][k][1][2][0][1]+P2[j-1][k][2][1][0][1]+P2[j][k][2][0][0][1]+V2[j-2][k][2][2][0][1]-V2[i+1][k][2][2][0][1];

                t1+=P1[i][k+1][0][2][1][0]+P1[i+1][k+1][1][2][1][0]+P1[j-1][k+1][2][1][1][0]+P1[j][k+1][2][0][1][0]+V1[j-2][k+1][2][2][1][0]-V1[i+1][k+1][2][2][1][0];
                t2+=P2[i][k+1][0][2][1][0]+P2[i+1][k+1][1][2][1][0]+P2[j-1][k+1][2][1][1][0]+P2[j][k+1][2][0][1][0]+V2[j-2][k+1][2][2][1][0]-V2[i+1][k+1][2][2][1][0];
                if(t1==1 && t2==1) ans++;
            }
            for(int k=1; k<=M-2; k++)
            {
                int t1=0, t2=0;
                t1+=P1[i][k][0][2][0][2]+P1[i+1][k][1][2][0][2]+P1[j-1][k][2][1][0][2]+P1[j][k][2][0][0][2]+V1[j-2][k][2][2][0][2]-V1[i+1][k][2][2][0][2];
                t2+=P2[i][k][0][2][0][2]+P2[i+1][k][1][2][0][2]+P2[j-1][k][2][1][0][2]+P2[j][k][2][0][0][2]+V2[j-2][k][2][2][0][2]-V2[i+1][k][2][2][0][2];

                t1+=P1[i][k+1][0][2][1][1]+P1[i+1][k+1][1][2][1][1]+P1[j-1][k+1][2][1][1][1]+P1[j][k+1][2][0][1][1]+V1[j-2][k+1][2][2][1][1]-V1[i+1][k+1][2][2][1][1];
                t2+=P2[i][k+1][0][2][1][1]+P2[i+1][k+1][1][2][1][1]+P2[j-1][k+1][2][1][1][1]+P2[j][k+1][2][0][1][1]+V2[j-2][k+1][2][2][1][1]-V2[i+1][k+1][2][2][1][1];
                
                t1+=P1[i][k+2][0][2][2][0]+P1[i+1][k+2][1][2][2][0]+P1[j-1][k+2][2][1][2][0]+P1[j][k+2][2][0][2][0]+V1[j-2][k+2][2][2][2][0]-V1[i+1][k+2][2][2][2][0];
                t2+=P2[i][k+2][0][2][2][0]+P2[i+1][k+2][1][2][2][0]+P2[j-1][k+2][2][1][2][0]+P2[j][k+2][2][0][2][0]+V2[j-2][k+2][2][2][2][0]-V2[i+1][k+2][2][2][2][0];
                if(t1==1 && t2==1) ans++;
            }

            for(int k=1; k<=M; k++)
            {
                if(k+1<=M) B11[k]+=P1[i][k][0][2][0][2]+P1[i][k+1][0][2][1][2]-H1[i][k+1][0][2][2][2];
                if(k-2>=0) B12[k]+=P1[i][k][0][2][2][0]+P1[i][k-1][0][2][2][1]+H1[i][k-2][0][2][2][2];              
                if(k+1<=M) B21[k]+=P2[i][k][0][2][0][2]+P2[i][k+1][0][2][1][2]-H2[i][k+1][0][2][2][2];
                if(k-2>=0) B22[k]+=P2[i][k][0][2][2][0]+P2[i][k-1][0][2][2][1]+H2[i][k-2][0][2][2][2];

                if(k+1<=M) B11[k]+=P1[i+1][k][1][2][0][2]+P1[i+1][k+1][1][2][1][2]-H1[i+1][k+1][1][2][2][2];
                if(k-2>=0) B12[k]+=P1[i+1][k][1][2][2][0]+P1[i+1][k-1][1][2][2][1]+H1[i+1][k-2][1][2][2][2];              
                if(k+1<=M) B21[k]+=P2[i+1][k][1][2][0][2]+P2[i+1][k+1][1][2][1][2]-H2[i+1][k+1][1][2][2][2];
                if(k-2>=0) B22[k]+=P2[i+1][k][1][2][2][0]+P2[i+1][k-1][1][2][2][1]+H2[i+1][k-2][1][2][2][2];
                
                if(k+1<=M) B11[k]+=P1[j][k][2][0][0][2]+P1[j][k+1][2][0][1][2]-H1[j][k+1][2][0][2][2];
                if(k-2>=0) B12[k]+=P1[j][k][2][0][2][0]+P1[j][k-1][2][0][2][1]+H1[j][k-2][2][0][2][2];              
                if(k+1<=M) B21[k]+=P2[j][k][2][0][0][2]+P2[j][k+1][2][0][1][2]-H2[j][k+1][2][0][2][2];
                if(k-2>=0) B22[k]+=P2[j][k][2][0][2][0]+P2[j][k-1][2][0][2][1]+H2[j][k-2][2][0][2][2];

                if(k+1<=M) B11[k]+=P1[j-1][k][2][1][0][2]+P1[j-1][k+1][2][1][1][2]-H1[j-1][k+1][2][1][2][2];
                if(k-2>=0) B12[k]+=P1[j-1][k][2][1][2][0]+P1[j-1][k-1][2][1][2][1]+H1[j-1][k-2][2][1][2][2];              
                if(k+1<=M) B21[k]+=P2[j-1][k][2][1][0][2]+P2[j-1][k+1][2][1][1][2]-H2[j-1][k+1][2][1][2][2];
                if(k-2>=0) B22[k]+=P2[j-1][k][2][1][2][0]+P2[j-1][k-1][2][1][2][1]+H2[j-1][k-2][2][1][2][2];
                
                if(k+1<=M) B11[k]+=(V1[j-2][k][2][2][0][2]-V1[i+1][k][2][2][0][2])+(V1[j-2][k+1][2][2][1][2]-V1[i+1][k+1][2][2][1][2])-(S1[j-2][k+1][2][2][2][2]-S1[i+1][k+1][2][2][2][2]);
                if(k-2>=0) B12[k]+=(V1[j-2][k][2][2][2][0]-V1[i+1][k][2][2][2][0])+(V1[j-2][k-1][2][2][2][1]-V1[i+1][k-1][2][2][2][1])+(S1[j-2][k-2][2][2][2][2]-S1[i+1][k-2][2][2][2][2]);
                if(k+1<=M) B21[k]+=(V2[j-2][k][2][2][0][2]-V2[i+1][k][2][2][0][2])+(V2[j-2][k+1][2][2][1][2]-V2[i+1][k+1][2][2][1][2])-(S2[j-2][k+1][2][2][2][2]-S2[i+1][k+1][2][2][2][2]);
                if(k-2>=0) B22[k]+=(V2[j-2][k][2][2][2][0]-V2[i+1][k][2][2][2][0])+(V2[j-2][k-1][2][2][2][1]-V2[i+1][k-1][2][2][2][1])+(S2[j-2][k-2][2][2][2][2]-S2[i+1][k-2][2][2][2][2]);
            }
            solve();
        }
        
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int naive(int, int, int, int)':
Main.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=1; i<V.size(); i++) if(abs(V[i].second.first-V[i-1].second.first)+abs(V[i].second.second-V[i-1].second.second)!=1) return false;
      |                  ~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:67:62: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);
      |                                                         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:73:62: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) scanf("%d", &A[j][i]);
      |                                                         ~~~~~^~~~~~~~~~~~~~~~

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