Submission #1180134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180134		niepamietamhasla	Sandcastle 2 (JOI22_ho_t5)	C++20	80 / 100	5104 ms	867960 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;

#define h [a][b][c][d]

vector<pair<int,int>> off = {{-1, 0}, {0, +1}, {1, 0}, {0, -1}};

vector<vector<int>> mv = {{1, 2, 4, 8}, {2, 4, 8, 1}, {4, 8, 1, 2}, {8, 1, 2, 4}};

vector<vector<int>> plansza;
gp_hash_table<int, int> mapa;
ll w = 0;

vector<vector<vector<vector<vector<vector<int>>>>>> ile;
vector<vector<vector<vector<vector<vector<int>>>>>> val;
vector<vector<vector<vector<vector<vector<int>>>>>> pref;

int prefsum(int i1, int j1, int i2, int j2, int a, int b, int c, int d){
    if(i1 > i2 or j1 > j2) return 0;
    return pref[i2][j2]h - pref[i1-1][j2]h - pref[i2][j1-1]h + pref[i1-1][j1-1]h;
}

int dodajpocz(int gl, int currs, int a, int b){
    if(b-a+1 == 1){
        return currs + val[gl][a][0][0][2][0] + val[gl+1][a][1][0][2][0];
    }
    else if(b-a+1 == 2){
        return currs + val[gl][a][0][1][2][0] + val[gl][b][0][0][2][1] + val[gl+1][a][1][1][2][0] + val[gl+1][b][1][0][2][1];
    }
    else if(b-a+1 == 3){
        return currs + val[gl][a][0][2][2][0] + val[gl][a+1][0][1][2][1] + val[gl][b][0][0][2][2] +
        val[gl+1][a][1][2][2][0] + val[gl+1][a+1][1][1][2][1] + val[gl+1][b][1][0][2][2];
    }
    else{
        return currs + val[gl][a][0][2][2][0] + val[gl][a+1][0][2][2][1] + val[gl][b][0][0][2][2] + val[gl][b-1][0][1][2][2] + prefsum(gl, a + 2, gl, b - 2, 0, 2, 2, 2) + 
        val[gl+1][a][1][2][2][0] + val[gl+1][a+1][1][2][2][1] + val[gl+1][b][1][0][2][2] + val[gl+1][b-1][1][1][2][2] + prefsum(gl + 1, a + 2, gl + 1, b - 2, 1, 2, 2, 2);
    }
}

int dodajmid(int gl, int a, int b){
    if(a == b){
        return val[gl][a][2][0][2][0];
    }
    else if(b-a+1 == 2){
        return val[gl][a][2][1][2][0] + val[gl][b][2][0][2][1];
    }
    else if(b-a+1 == 3){
        return val[gl][a][2][2][2][0] + val[gl][a+1][2][1][2][1] + val[gl][b][2][0][2][2];
    }
    else{
        return val[gl][a][2][2][2][0] + val[gl][a+1][2][2][2][1] + val[gl][b][2][0][2][2] + val[gl][b-1][2][1][2][2] + prefsum(gl, a + 2, gl, b - 2, 2, 2, 2, 2);
    }
}

int dodajkon(int gl, int currs, int a, int b){
    if(a == b){
        return currs + val[gl][a][2][0][0][0] + val[gl-1][a][2][0][1][0];
    }
    else if(b-a+1 == 2){
        return currs + val[gl][a][2][1][0][0] + val[gl][b][2][0][0][1] + val[gl-1][a][2][1][1][0] + val[gl-1][b][2][0][1][1];
    }
    else if(b-a+1 == 3){
        return currs + val[gl][a][2][2][0][0] + val[gl][a+1][2][1][0][1] + val[gl][b][2][0][0][2] + 
        val[gl-1][a][2][2][1][0] + val[gl-1][a+1][2][1][1][1] + val[gl-1][b][2][0][1][2];
    }
    else{
        return currs + val[gl][a][2][2][0][0] + val[gl][a+1][2][2][0][1] + val[gl][b][2][0][0][2] + val[gl][b-1][2][1][0][2] + prefsum(gl, a + 2, gl, b - 2, 2, 2, 0, 2) + 
        val[gl-1][a][2][2][1][0] + val[gl-1][a+1][2][2][1][1] + val[gl-1][b][2][0][1][2] + val[gl-1][b-1][2][1][1][2] + prefsum(gl - 1, a + 2, gl - 1, b - 2, 2, 2, 1, 2);
    }
}

int sprawdz(int x1, int y1, int x2, int y2){
    ll S = 0;
    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " prostokat\n";
    
    for(int i = x1; i <= x2; ++i){
        //cout << "#\n";
        int a = min(i - x1, 2);
        int c = min(x2 - i, 2);
        //cout << a << " " << c << " ab\n";
        if(y2 - y1 + 1 >= 4){
            S += val[i][y1][a][2][c][0] + val[i][y1+1][a][2][c][1] + val[i][y2][a][0][c][2] + val[i][y2-1][a][1][c][2] + prefsum(i, y1 + 2, i, y2 - 2, a, 2, c, 2);
        }
        else{
            for(int j = y1; j <= y2; ++j){
                //cout << "# ";
                int d = min(j - y1, 2);
                int b = min(y2 - j, 2);
                //cout << b << " " << d << " " << j << " bd\n";
                S += val[i][j][a][b][c][d];
            }
            //cout << "\n";
        }
    }
    //cout << S << " S\n";
    return S == 1;
}

int main(){
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    int t[n+2][m+2];
    for(int i = 0; i < n+2; ++i){
        for(int j = 0; j < m+2; ++j){
            t[i][j] = 0;
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> t[i][j];
        }
    }
    if(n < m){
        plansza.resize(m+2);
        for(int i = 0; i < m+2; ++i){
            plansza[i].resize(n+2);
        }
        for(int i = 0; i < m+2; ++i){
            for(int j = 0; j < n+2; ++j){
                plansza[i][j] = 0;  
            }
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                //cout << j << " " << n-i+1 << " " << t[i][j] << " ust\n";
                plansza[j][n-i+1] = t[i][j];
            }
        }
        swap(n, m);
    }
    else{
        plansza.resize(n+2);
        for(int i = 0; i < n+2; ++i){
            plansza[i].resize(m+2);
        }
        for(int i = 0; i < n+2; ++i){
            for(int j = 0; j < m+2; ++j){
                plansza[i][j] = 0;  
            }
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                plansza[i][j] = t[i][j];
            }
        }
    }
    // cout << n << " " << m << "\n";
    // for(int i = 1; i <= n; ++i){
    //     for(int j = 1; j <= m; ++j){
    //         cout << plansza[i][j] << " ";
    //     }
    //     cout << "\n";
    // }


    val.resize(n + 2, vector<vector<vector<vector<vector<int>>>>>(m + 2, vector<vector<vector<vector<int>>>>(3, vector<vector<vector<int>>>(3, vector<vector<int>>(3, vector<int>(3, 0))))));
    pref.resize(n + 2, vector<vector<vector<vector<vector<int>>>>>(m + 2, vector<vector<vector<vector<int>>>>(3, vector<vector<vector<int>>>(3, vector<vector<int>>(3, vector<int>(3, 0))))));
    ile.resize(n + 2, vector<vector<vector<vector<vector<int>>>>>(m + 2, vector<vector<vector<vector<int>>>>(3, vector<vector<vector<int>>>(3, vector<vector<int>>(3, vector<int>(3, 0))))));
    

    int maks[n+2][m+2][16];
    for(int i = 0; i < n+2; ++i){
        for(int j = 0; j < m+2; ++j){
            for(int k = 0; k < 16; ++k){
                maks[i][j][k] = 0;
            }
        }
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            for(int k = 0; k < 16; ++k){
                for(int l = 0; l < 4; ++l){
                    if(((1 << l) & k) != 0) {
                        if(plansza[i+off[l].first][j+off[l].second] > plansza[i][j]) continue;
                        maks[i][j][k] = max(maks[i][j][k], plansza[i+off[l].first][j+off[l].second]);
                    }
                }
            }
        }
    }

    for(int i = 0; i < n+2; ++i){
        for(int j = 0; j < m+2; ++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){
                            pref[i][j][a][b][c][d] = 0;
                            val[i][j][a][b][c][d] = 0;
                            ile[i][j][a][b][c][d] = 0;
                        }
                    }
                }
            }
        }
    }

    for(int i = 1; i <= n; ++i){
        for(int j = 1; 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){
                            array<int, 4> e = {a, b, c, d};
                            for(int k = 0; k < 4; ++k){
                                if(e[k] == 0) continue;
                                if(k == 0 and i == 1) continue;
                                if(k == 1 and j == m) continue;
                                if(k == 2 and i == n) continue;
                                if(k == 4 and j == 1) continue;
                                if(i == 1 and j == 1 and a == 0 and b == 0 and c == 1 and d == 0){
                                    //cout << k << " k\n";
                                }
                                int w = 0;
                                w += mv[k][2];
                                if(e[k] == 2) w += mv[k][0];
                                if(e[(k - 1 + 4) % 4] != 0) w += mv[k][3];
                                if(e[(k + 1) % 4] != 0) w += mv[k][1];
                                if(i == 1 and j == 1 and a == 0 and b == 0 and c == 1 and d == 0){
                                    //cout << w << " w\n";
                                    //cout << maks[i+off[k].first][j+off[k].second][w] << " m\n";
                                }
                                if(maks[i+off[k].first][j+off[k].second][w] == plansza[i][j]) ile[i][j][a][b][c][d]++;
                            }
                            val[i][j][a][b][c][d] += (ile[i][j][a][b][c][d] != 1);
                            //if(b == 0 and d == 0) cout << i << " " << j << " " << a << " " << b << " " << c << " " << d << " " << ile[i][j][a][b][c][d] << " V\n";
                        }
                        //cout << "\n";
                    }
                    //cout << "\n";
                }
                //cout << "\n";
            }
            //cout << "\n";
        }
    }
    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){
                    for(int i = 1; i <= n; ++i){
                        for(int j = 1; j <= m; ++j){
                            pref[i][j][a][b][c][d] = pref[i-1][j][a][b][c][d] + pref[i][j-1][a][b][c][d] - pref[i-1][j-1][a][b][c][d] + val[i][j][a][b][c][d];
                        }
                    }
                }
            }
        }
    }

    for(int a = 1; a <= m; ++a){
        for(int b = a; b <= m; ++b){
            for(int i = 1; i <= min(3, n); ++i){
                for(int j = i; j <= min(3, n); ++j){
                    w += sprawdz(i, a, j, b);
                }
            }
            if(n <= 3) continue;
            
            //cout << a << " " << b << " przed\n";
            ll currs2 = dodajmid(1, a, b) + dodajmid(2, a, b);
            ll currs1 = -currs2;
            //cout << currs1 << " " << currs2 << " curr\n";
            mapa.clear();
            for(int i = 4; i <= n; ++i){
                mapa[dodajpocz(i - 3, currs1, a, b)]++;
                w += mapa[-dodajkon(i, currs2, a, b) + 1];
                w += sprawdz(i - 2, a, i, b);
                w += sprawdz(i - 1, a, i, b);
                w += sprawdz(i, a, i, b);
                currs2 += dodajmid(i - 1, a, b);
                currs1 -= dodajmid(i - 1, a, b);
                //cout << currs1 << " " << currs2 << " curr\n";
                //cout << w << " w\n";
            }
        }
    }
    cout << w << "\n";
    return 0;
}

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