Submission #1179823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179823		Szymon_Pilipczuk	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	3989 ms	127696 KiB

Main

#include <bits/stdc++.h>
using namespace std;
long long ans =0;
vector<vector<vector<vector<vector<vector<int>>>>>> spv;
int spc(pair<int,int> q1,pair<int,int> q2,int a,int b,int c,int d)
{
    if(q1.first > q2.first || q1.second > q2.second)
    {
        return 0;
    }
    int ans = spv[q2.first][q2.second][a][b][c][d];
    if(q1.first != 0 && q1.second!= 0)
    {
        ans += spv[q1.first-1][q1.second-1][a][b][c][d];
    }
    if(q1.first!= 0)
    {
        ans-= spv[q1.first-1][q2.second][a][b][c][d];
    }
    if(q1.second!= 0)
    {
        ans-=spv[q2.first][q1.second-1][a][b][c][d];
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);
    int n,m;
    cin>>n>>m;
    bool ch = n > m;
    if(ch)
    {
        swap(n,m);
    }
    vector<vector<int>> v(n);
    int v2[n][m][3][3][3][3];
    for(int i = 0;i<n;i++)
    {
        v[i].resize(m);
    }
    if(ch)
    {
        for(int j = 0;j<m;j++)
        {
            for(int i = 0;i<n;i++)
            {
                cin>>v[i][j];
            }
        }
    }
    else
    {
        for(int i = 0 ;i<n;i++)
        {
            for(int j = 0;j<m;j++)
            {
                cin>>v[i][j];
            }
        }
    }
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++)
        {

            for(int a = 0;a<3;a++)
            {
                for(int b = 0;b<3;b++)
                {
                    for(int c = 0;c<3;c++)
                    {
                        for(int d = 0;d<3;d++)
                        {
                            int ct = 0;
                            int mx = 0;
                            if((a == 1 && i > 0) ||(a > 0 &&i == 1))
                            {
                                if(d != 0 &&j != 0 && v[i-1][j] > v[i-1][j-1])
                                {
                                    mx = max(mx,v[i-1][j-1]);
                                }
                                if(b!= 0 &&j != m-1 && v[i-1][j] > v[i-1][j+1])
                                {
                                    mx = max(mx,v[i-1][j+1]);
                                }
                            }
                            else if(a == 2 &&i > 0)
                            {
                                if(v[i-1][j] > v[i-2][j])
                                {
                                    mx = max(mx,v[i-2][j]);
                                }
                                if(d !=  0 &&j != 0 && v[i-1][j] > v[i-1][j-1])
                                {
                                    mx = max(mx,v[i-1][j-1]);
                                }
                                if(b != 0 &&j != m-1 && v[i-1][j] > v[i-1][j+1])
                                {
                                    mx = max(mx,v[i-1][j+1]);
                                }
                            }
                            if(a >  0 && i!= 0 && v[i-1][j] > v[i][j] && v[i][j] > mx)
                            {
                                ct++;
                            }
                            mx = 0;
                            if(b > 0 && j < m-1)
                            {
                                if(a != 0 &&i != 0 && v[i][j+1] > v[i-1][j+1])
                                {
                                    mx = max(mx,v[i-1][j+1]);
                                }
                                if(c != 0 &&i != n-1 && v[i][j+1] > v[i+1][j+1])
                                {
                                    mx = max(mx,v[i+1][j+1]);
                                }
                            }
                            if(b == 2 && j < m-2)
                            {
                                if(v[i][j+1] > v[i][j+2])
                                {
                                    mx = max(mx,v[i][j+2]);
                                }
                            }
                            if(b >  0 && j!= m-1 && v[i][j+1] > v[i][j] && v[i][j] > mx)
                            {
                                ct++;
                            }
                            mx = 0;
                            if(c > 0 && i <n-1)
                            {
                                if(d != 0 &&j != 0 && v[i+1][j] > v[i+1][j-1])
                                {
                                    mx = max(mx,v[i+1][j-1]);
                                }
                                if(b!= 0 &&j != m-1 && v[i+1][j] > v[i+1][j+1])
                                {
                                    mx = max(mx,v[i+1][j+1]);
                                }
                            }
                            if(c == 2 && i < n-2)
                            {
                                if(v[i+1][j] > v[i+2][j])
                                {
                                    mx = max(mx,v[i+2][j]);
                                }
                            }
                            if(c >  0 && i != n-1 && v[i+1][j] > v[i][j] && v[i][j] > mx)
                            {
                                ct++;
                            }
                            mx = 0;
                            if(d > 0 && j > 0)
                            {
                                if(a!= 0 &&i != 0 && v[i][j-1] > v[i-1][j-1])
                                {
                                    mx = max(mx,v[i-1][j-1]);
                                }
                                if(c != 0 &&i != n-1 && v[i][j-1] > v[i+1][j-1])
                                {
                                    mx = max(mx,v[i+1][j-1]);
                                }
                            }
                            if(d == 2 && j > 1)
                            {
                                if(v[i][j-1] > v[i][j-2])
                                {
                                    mx = max(mx,v[i][j-2]);
                                }
                            }
                            if(d >  0 && j != 0 && v[i][j-1] > v[i][j] && v[i][j] > mx)
                            {
                                ct++;
                            }
                            if(ct == 0)
                            {
                                v2[i][j][a][b][c][d] = 1;
                            }
                            else
                            {
                                v2[i][j][a][b][c][d] = 0;
                            }

                        }
                    }
                }
            }
        }
    }
    int sp[n][m][3][3][3][3];
    for(int i = 0;i<n;i++)
    {
        for(int j = 0;j<m;j++)
        {
            for(int a = 0;a<3;a++)
            {
                for(int b = 0;b<3;b++)
                {
                    for(int c = 0;c<3;c++)
                    {
                        for(int d = 0;d<3;d++)
                        {
                            int ct = v2[i][j][a][b][c][d];
                            if(i != 0)
                            {
                                ct+= sp[i-1][j][a][b][c][d];
                            }
                            if(j != 0)
                            {
                                ct+= sp[i][j-1][a][b][c][d];
                            }
                            if(i != 0 && j != 0)
                            {
                                ct-= sp[i-1][j-1][a][b][c][d];
                            }
                            sp[i][j][a][b][c][d] = ct;
                        }
                    }
                }
            }
        }
    }
    spv.resize(n);
    for(int i =0;i<n;i++)
    {
        spv[i].resize(m);
        for(int j = 0;j<m;j++)
        {
            spv[i][j].resize(3);
            for(int a = 0;a<3;a++)
            {
                spv[i][j][a].resize(3);
                for(int b =0 ;b<3;b++)
                {
                    spv[i][j][a][b].resize(3);
                    for(int c = 0;c<3;c++)
                    {
                        spv[i][j][a][b][c].resize(3);
                        for(int d = 0;d<3;d++)
                        {
                            spv[i][j][a][b][c][d]= sp[i][j][a][b][c][d];
                        }
                    }
                }
            }
        }
    }
    for(int i = 0;i<n;i++)
    {
        for(int j = i+3;j<n;j++)
        {
            unordered_map<int,int> mm;
            for(int q = 3;q<m;q++)
            {
                int ct = 0;
                ct+=spc({i,0},{i,q-2},0,2,2,2);
                ct+=spc({i+1,0},{i+1,q-2},1,2,2,2);
                ct+=spc({j,0},{j,q-2},2,2,0,2);
                ct+=spc({j-1,0},{j-1,q-2},2,2,1,2);
                ct+=spc({i+2,0},{j-2,q-2},2,2,2,2);
                ct-=spc({i+2,q-2},{j-2,q-2},2,2,2,1);
                ct-=spc({i+2,q-3},{j-2,q-3},2,2,2,0);
                ct-=spc({i+1,q-2},{i+1,q-2},1,2,2,1);
                ct-=spc({i,q-2},{i,q-2},0,2,2,1);
                ct-=spc({i+1,q-3},{i+1,q-3},1,2,2,0);
                ct-=spc({i,q-3},{i,q-3},0,2,2,0);
                ct-=spc({j-1,q-2},{j-1,q-2},2,2,1,1);
                ct-=spc({j,q-2},{j,q-2},2,2,0,1);
                ct-=spc({j-1,q-3},{j-1,q-3},2,2,1,0);
                ct-=spc({j,q-3},{j,q-3},2,2,0,0);
                mm[ct]++;
                ct = 0;
                ct+=spc({i,0},{i,q-2},0,2,2,2);
                ct+=spc({i+1,0},{i+1,q-2},1,2,2,2);
                ct+=spc({j,0},{j,q-2},2,2,0,2);
                ct+=spc({j-1,0},{j-1,q-2},2,2,1,2);
                ct+=spc({i+2,0},{j-2,q-2},2,2,2,2);
                ct+=spc({i+2,q-1},{j-2,q-1},2,1,2,2);
                ct+=spc({i+2,q},{j-2,q},2,0,2,2);
                ct+=spc({i+1,q-1},{i+1,q-1},1,1,2,2);
                ct+=spc({i,q-1},{i,q-1},0,1,2,2);
                ct+=spc({i+1,q},{i+1,q},1,0,2,2);
                ct+=spc({i,q},{i,q},0,0,2,2);
                ct+=spc({j-1,q-1},{j-1,q-1},2,1,1,2);
                ct+=spc({j,q-1},{j,q-1},2,1,0,2);
                ct+=spc({j-1,q},{j-1,q},2,0,1,2);
                ct+=spc({j,q},{j,q},2,0,0,2);
                ans+=mm[ct-1];
            }
        }
    }
    for(int i = 0;i<n-2;i++)
    {
        unordered_map<int,int> mm;
        for(int q = 3;q<m;q++)
        {
            int ct = 0;
            ct+=spc({i,0},{i,q-2},0,2,2,2);
            ct+=spc({i+1,0},{i+1,q-2},1,2,1,2);
            ct+=spc({i+2,0},{i+2,q-2},2,2,0,2);
            ct-=spc({i,q-3},{i,q-3},0,2,2,0);
            ct-=spc({i,q-2},{i,q-2},0,2,2,1);
            ct-=spc({i+1,q-3},{i+1,q-3},1,2,1,0);
            ct-=spc({i+1,q-2},{i+1,q-2},1,2,1,1);
            ct-=spc({i+2,q-3},{i+2,q-3},2,2,0,0);
            ct-=spc({i+2,q-2},{i+2,q-2},2,2,0,1);
            mm[ct]++;
            ct = 0;
            ct+=spc({i,0},{i,q-2},0,2,2,2);
            ct+=spc({i+1,0},{i+1,q-2},1,2,1,2);
            ct+=spc({i+2,0},{i+2,q-2},2,2,0,2);
            ct+=spc({i,q-1},{i,q-1},0,1,2,2);
            ct+=spc({i+1,q-1},{i+1,q-1},1,1,1,2);
            ct+=spc({i+2,q-1},{i+2,q-1},2,1,0,2);
            ct+=spc({i,q},{i,q},0,0,2,2);
            ct+=spc({i+1,q},{i+1,q},1,0,1,2);
            ct+=spc({i+2,q},{i+2,q},2,0,0,2);
            ans+=mm[ct-1];
        }
    }
    for(int i = 0;i<n-1;i++)
    {
        unordered_map<int,int> mm;
        for(int q= 3;q<m;q++)
        {
            int ct = 0;
            ct+=spc({i,0},{i,q-2},0,2,1,2);
            ct+=spc({i+1,0},{i+1,q-2},1,2,0,2);
            ct-=spc({i,q-2},{i,q-2},0,2,1,1);
            ct-=spc({i,q-3},{i,q-3},0,2,1,0);
            ct-=spc({i+1,q-2},{i+1,q-2},1,2,0,1);
            ct-=spc({i+1,q-3},{i+1,q-3},1,2,0,0);
            mm[ct]++;
            ct = 0;
            ct+=spc({i,0},{i,q-2},0,2,1,2);
            ct+=spc({i+1,0},{i+1,q-2},1,2,0,2);
            ct+=spc({i,q-1},{i,q-1},0,1,1,2);
            ct+=spc({i+1,q-1},{i+1,q-1},1,1,0,2);
            ct+=spc({i,q},{i,q},0,0,1,2);
            ct+=spc({i+1,q},{i+1,q},1,0,0,2);
            ans+=mm[ct-1];
        }
    }
    for(int i = 0;i<n;i++)
    {
        unordered_map<int,int> mm;
        for(int q = 3;q<m;q++)
        {
            int ct = 0;
            ct+=spc({i,0},{i,q-2},0,2,0,2);
            ct-=spc({i,q-3},{i,q-3},0,2,0,0);
            ct-=spc({i,q-2},{i,q-2},0,2,0,1);
            mm[ct]++;
            ct = 0;
            ct+=spc({i,0},{i,q-2},0,2,0,2);
            ct+=spc({i,q-1},{i,q-1},0,1,0,2);
            ct+=spc({i,q},{i,q},0,0,0,2);
            ans+=mm[ct-1];
        }
    }
    for(int j = 0;j<m;j++)
    {
        for(int b =0;b<3;b++)
        {
            if(b+j >=m)
            {
                continue;
            }
            unordered_map<int,int> mm;
            for(int i = 3;i<n;i++)
            {
                int ct = 0;
                for(int a =0 ;a<=b;a++)
                {
                    ct+=spc({0,j+a},{i-2,j+a},2,b-a,2,a);
                    ct-=spc({i-2,j+a},{i-2,j+a},1,b-a,2,a);
                    ct-=spc({i-3,j+a},{i-3,j+a},0,b-a,2,a);
                }
                mm[ct]++;
                ct = 0;
                for(int a = 0;a<=b;a++)
                {
                    ct+=spc({0,j+a},{i-2,j+a},2,b-a,2,a);
                    ct+=spc({i-1,j+a},{i-1,j+a},2,b-a,1,a);
                    ct+=spc({i,j+a},{i,j+a},2,b-a,0,a);
                }

                ans+=mm[ct-1];
            }
        }
    }
    for(int i =0 ;i<n;i++)
    {
        for(int j = 0;j<m;j++)
        {
            for(int a = 0;a<3;a++)
            {
                for(int b= 0 ;b<3;b++)
                {
                    if(a+i>=n || b+j >=m)
                    {
                        continue;
                    }
                    int ct = 0;
                    for(int c= 0 ;c<=a;c++)
                    {
                        for(int d= 0 ;d<=b;d++)
                        {
                            ct+=spc({i+c,j+d},{i+c,j+d},c,b-d,a-c,d);
                            //       1   1     1   1    1 0   0   0
                            //cout<<i+c<<" "<<j+d<<" "<<c<<" "<<b-d<<" "<<a-c<<" "<<d<<"\n";
                            //cout<<ct<<"\n";
                        }
                    }
                    //cout<<i<<" "<<j<<" "<<a<<" "<<b<<" "<<ct<<"\n";
                    if(ct == 1)
                    {
                        ans++;
                    }
                }
            }
        }
    }
    cout<<ans<<"\n";
}

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