Submission #858583

#	Time	Username	Problem	Language	Result	Execution time	Memory
858583		arnold518	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	743 ms	207128 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>> P, S, H, V;
vector<int> B1, B2;

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;
}

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;

int MM[MAXN*6+10];
void solve()
{
    for(int i=4; i<=M; i++)
    {
        MM[B1[i-3]+MAXN*3]++;
        ans+=MM[2-B2[i]+MAXN*3];
    }
    for(int i=1; i<=M; i++) MM[B1[i]+MAXN*3]=0;
}

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]);
    }
    P=S=H=V=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) P[i][j][pi][qi][pj][qj]++;

                    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) P[i][j][pi][qi][pj][qj]++;
                }
            }
        }
    }
    
    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++)
                {
                    S[i][j][pi][qi][pj][qj]=P[i][j][pi][qi][pj][qj]+S[i-1][j][pi][qi][pj][qj]+S[i][j-1][pi][qi][pj][qj]-S[i-1][j-1][pi][qi][pj][qj];
                    H[i][j][pi][qi][pj][qj]=P[i][j][pi][qi][pj][qj]+H[i][j-1][pi][qi][pj][qj];
                    V[i][j][pi][qi][pj][qj]=P[i][j][pi][qi][pj][qj]+V[i-1][j][pi][qi][pj][qj];
                }
            }
        }
    }

    for(int i=1; i<=N; i++) for(int j=i; j<=N; j++)
    {
        B1=B2=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) B1[k]+=P[i][k][0][0][0][2]+P[i][k+1][0][0][1][2]-H[i][k+1][0][0][2][2];
                if(k-2>=0) B2[k]+=P[i][k][0][0][2][0]+P[i][k-1][0][0][2][1]+H[i][k-2][0][0][2][2];
            }
            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) B1[k]+=P[i][k][0][1][0][2]+P[i][k+1][0][1][1][2]-H[i][k+1][0][1][2][2];
                if(k-2>=0) B2[k]+=P[i][k][0][1][2][0]+P[i][k-1][0][1][2][1]+H[i][k-2][0][1][2][2];

                if(k+1<=M) B1[k]+=P[i+1][k][1][0][0][2]+P[i+1][k+1][1][0][1][2]-H[i+1][k+1][1][0][2][2];
                if(k-2>=0) B2[k]+=P[i+1][k][1][0][2][0]+P[i+1][k-1][1][0][2][1]+H[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) B1[k]+=P[i][k][0][2][0][2]+P[i][k+1][0][2][1][2]-H[i][k+1][0][2][2][2];
                if(k-2>=0) B2[k]+=P[i][k][0][2][2][0]+P[i][k-1][0][2][2][1]+H[i][k-2][0][2][2][2];

                if(k+1<=M) B1[k]+=P[i+1][k][1][1][0][2]+P[i+1][k+1][1][1][1][2]-H[i+1][k+1][1][1][2][2];
                if(k-2>=0) B2[k]+=P[i+1][k][1][1][2][0]+P[i+1][k-1][1][1][2][1]+H[i+1][k-2][1][1][2][2];

                if(k+1<=M) B1[k]+=P[i+2][k][2][0][0][2]+P[i+2][k+1][2][0][1][2]-H[i+2][k+1][2][0][2][2];
                if(k-2>=0) B2[k]+=P[i+2][k][2][0][2][0]+P[i+2][k-1][2][0][2][1]+H[i+2][k-2][2][0][2][2];
            }
            solve();
        }
        else
        {
            for(int k=1; k<=M; k++)
            {
                int t=0;
                t+=P[i][k][0][2][0][0]+P[i+1][k][1][2][0][0]+P[j-1][k][2][1][0][0]+P[j][k][2][0][0][0]+V[j-2][k][2][2][0][0]-V[i+1][k][2][2][0][0];
                if(t==2) ans++;
            }
            for(int k=1; k<=M-1; k++)
            {
                int t=0;
                t+=P[i][k][0][2][0][1]+P[i+1][k][1][2][0][1]+P[j-1][k][2][1][0][1]+P[j][k][2][0][0][1]+V[j-2][k][2][2][0][1]-V[i+1][k][2][2][0][1];
                t+=P[i][k+1][0][2][1][0]+P[i+1][k+1][1][2][1][0]+P[j-1][k+1][2][1][1][0]+P[j][k+1][2][0][1][0]+V[j-2][k+1][2][2][1][0]-V[i+1][k+1][2][2][1][0];
                if(t==2) ans++;
            }
            for(int k=1; k<=M-2; k++)
            {
                int t=0;
                t+=P[i][k][0][2][0][2]+P[i+1][k][1][2][0][2]+P[j-1][k][2][1][0][2]+P[j][k][2][0][0][2]+V[j-2][k][2][2][0][2]-V[i+1][k][2][2][0][2];
                t+=P[i][k+1][0][2][1][1]+P[i+1][k+1][1][2][1][1]+P[j-1][k+1][2][1][1][1]+P[j][k+1][2][0][1][1]+V[j-2][k+1][2][2][1][1]-V[i+1][k+1][2][2][1][1];
                t+=P[i][k+2][0][2][2][0]+P[i+1][k+2][1][2][2][0]+P[j-1][k+2][2][1][2][0]+P[j][k+2][2][0][2][0]+V[j-2][k+2][2][2][2][0]-V[i+1][k+2][2][2][2][0];
                if(t==2) ans++;
            }

            for(int k=1; k<=M; k++)
            {
                if(k+1<=M) B1[k]+=P[i][k][0][2][0][2]+P[i][k+1][0][2][1][2]-H[i][k+1][0][2][2][2];
                if(k-2>=0) B2[k]+=P[i][k][0][2][2][0]+P[i][k-1][0][2][2][1]+H[i][k-2][0][2][2][2];

                if(k+1<=M) B1[k]+=P[i+1][k][1][2][0][2]+P[i+1][k+1][1][2][1][2]-H[i+1][k+1][1][2][2][2];
                if(k-2>=0) B2[k]+=P[i+1][k][1][2][2][0]+P[i+1][k-1][1][2][2][1]+H[i+1][k-2][1][2][2][2];
                
                if(k+1<=M) B1[k]+=P[j][k][2][0][0][2]+P[j][k+1][2][0][1][2]-H[j][k+1][2][0][2][2];
                if(k-2>=0) B2[k]+=P[j][k][2][0][2][0]+P[j][k-1][2][0][2][1]+H[j][k-2][2][0][2][2];

                if(k+1<=M) B1[k]+=P[j-1][k][2][1][0][2]+P[j-1][k+1][2][1][1][2]-H[j-1][k+1][2][1][2][2];
                if(k-2>=0) B2[k]+=P[j-1][k][2][1][2][0]+P[j-1][k-1][2][1][2][1]+H[j-1][k-2][2][1][2][2];
                
                if(k+1<=M) B1[k]+=(V[j-2][k][2][2][0][2]-V[i+1][k][2][2][0][2])+(V[j-2][k+1][2][2][1][2]-V[i+1][k+1][2][2][1][2])-(S[j-2][k+1][2][2][2][2]-S[i+1][k+1][2][2][2][2]);
                if(k-2>=0) B2[k]+=(V[j-2][k][2][2][2][0]-V[i+1][k][2][2][2][0])+(V[j-2][k-1][2][2][2][1]-V[i+1][k-1][2][2][2][1])+(S[j-2][k-2][2][2][2][2]-S[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:38: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]
   38 |     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:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf("%d%d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:61:62: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) scanf("%d", &A[i][j]);
      |                                                         ~~~~~^~~~~~~~~~~~~~~~
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<=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