Submission #1180305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180305		niepamietamhasla	Sandcastle 2 (JOI22_ho_t5)	C++20	9 / 100	288 ms	177596 KiB

Main

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

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<int>>> pref;
vector<vector<vector<int>>> ile;
vector<vector<vector<int>>> val;

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

int dodajpocz(int gl, int currs, int a, int b){
    if(b - a + 1 == 1){
        return currs 
            + val[gl][a][6]    // [0][0][2][0]
            + val[gl+1][a][33]; // [1][0][2][0]
    }
    else if(b - a + 1 == 2){
        return currs 
            + val[gl][a][15]    // [0][1][2][0]
            + val[gl][b][7]     // [0][0][2][1]
            + val[gl+1][a][42]  // [1][1][2][0]
            + val[gl+1][b][34]; // [1][0][2][1]
    }
    else if(b - a + 1 == 3){
        return currs 
            + val[gl][a][24]    // [0][2][2][0]
            + val[gl][a+1][16]  // [0][1][2][1]
            + val[gl][b][8]     // [0][0][2][2]
            + val[gl+1][a][51]  // [1][2][2][0]
            + val[gl+1][a+1][43] // [1][1][2][1]
            + val[gl+1][b][35]; // [1][0][2][2]
    }
    else{
        return currs 
            + val[gl][a][24]     // [0][2][2][0]
            + val[gl][a+1][25]   // [0][2][2][1]
            + val[gl][b][8]      // [0][0][2][2]
            + val[gl][b-1][17]   // [0][1][2][2]
            + prefsum(gl, a + 2, gl, b - 2, 24) // [0][2][2][2]
            + val[gl+1][a][51]   // [1][2][2][0]
            + val[gl+1][a+1][52] // [1][2][2][1]
            + val[gl+1][b][35]   // [1][0][2][2]
            + val[gl+1][b-1][44] // [1][1][2][2]
            + prefsum(gl + 1, a + 2, gl + 1, b - 2, 53); // [1][2][2][2]
    }
}


int dodajmid(int gl, int a, int b){
    if(a == b){
        return val[gl][a][60]; // [2][0][2][0]
    }
    else if(b - a + 1 == 2){
        return val[gl][a][69]   // [2][1][2][0]
             + val[gl][b][61];  // [2][0][2][1]
    }
    else if(b - a + 1 == 3){
        return val[gl][a][78]    // [2][2][2][0]
             + val[gl][a+1][70]  // [2][1][2][1]
             + val[gl][b][62];   // [2][0][2][2]
    }
    else{
        return val[gl][a][78]     // [2][2][2][0]
             + val[gl][a+1][79]   // [2][2][2][1]
             + val[gl][b][62]     // [2][0][2][2]
             + val[gl][b-1][71]   // [2][1][2][2]
             + prefsum(gl, a + 2, gl, b - 2, 80); // [2][2][2][2]
    }
}


int dodajkon(int gl, int currs, int a, int b){
    if(a == b){
        return currs 
            + val[gl][a][54]    // [2][0][0][0]
            + val[gl-1][a][57]; // [2][0][1][0]
    }
    else if(b - a + 1 == 2){
        return currs 
            + val[gl][a][63]     // [2][1][0][0]
            + val[gl][b][55]     // [2][0][0][1]
            + val[gl-1][a][66]   // [2][1][1][0]
            + val[gl-1][b][58];  // [2][0][1][1]
    }
    else if(b - a + 1 == 3){
        return currs 
            + val[gl][a][72]     // [2][2][0][0]
            + val[gl][a+1][64]   // [2][1][0][1]
            + val[gl][b][56]     // [2][0][0][2]
            + val[gl-1][a][75]   // [2][2][1][0]
            + val[gl-1][a+1][67] // [2][1][1][1]
            + val[gl-1][b][59];  // [2][0][1][2]
    }
    else{
        return currs 
            + val[gl][a][72]      // [2][2][0][0]
            + val[gl][a+1][73]    // [2][2][0][1]
            + val[gl][b][56]      // [2][0][0][2]
            + val[gl][b-1][65]    // [2][1][0][2]
            + prefsum(gl, a + 2, gl, b - 2, 74) // [2][2][0][2]
            + val[gl-1][a][75]    // [2][2][1][0]
            + val[gl-1][a+1][76]  // [2][2][1][1]
            + val[gl-1][b][59]    // [2][0][1][2]
            + val[gl-1][b-1][68]  // [2][1][1][2]
            + prefsum(gl - 1, a + 2, gl - 1, b - 2, 77); // [2][2][1][2]
    }
}

int sprawdz(int x1, int y1, int x2, int y2){
    //cout << x1 << " " << y1 << " " << x2 << " " << y2 << " xy\n";
    ll S = 0;

    for(int i = x1; i <= x2; ++i){
        int a = min(i - x1, 2);
        int c = min(x2 - i, 2);

        if(y2 - y1 + 1 >= 4){
            S += val[i][y1][27*a + 18 + 3*c + 0]     // [a][2][c][0]
               + val[i][y1+1][27*a + 18 + 3*c + 1]   // [a][2][c][1]
               + val[i][y2][27*a + 0 + 3*c + 2]      // [a][0][c][2]
               + val[i][y2-1][27*a + 9 + 3*c + 2]    // [a][1][c][2]
               + prefsum(i, y1 + 2, i, y2 - 2, 27*a + 18 + 3*c + 2); // [a][2][c][2]
        }
        else{
            for(int j = y1; j <= y2; ++j){
                int d = min(j - y1, 2);
                int b = min(y2 - j, 2);
                S += val[i][j][27*a + 9*b + 3*c + d];
            }
        }
    }

    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<int>> (m+2, vector<int> (81, 0)));
    pref.resize(n+2, vector<vector<int>> (m+2, vector<int> (81, 0)));
    ile.resize(n+2, vector<vector<int>> (m+2, vector<int> (81, 0)));
    
    for(int i = 0; i < n+2; ++i){
        for(int j = 0; j < m+2; ++j){
            for(int k = 0; k < 81; ++k){
                val[i][j][k] = 0;
                ile[i][j][k] = 0;
                pref[i][j][k] = 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 = 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][27*a+9*b+3*c+d]++;
                            }
                            val[i][j][27*a+9*b+3*c+d] += (ile[i][j][27*a+9*b+3*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 k = 0; k < 81; ++k){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= m; ++j){
                pref[i][j][k] = pref[i-1][j][k] + pref[i][j-1][k] - pref[i-1][j-1][k] + val[i][j][k];
            }
        }
    }

    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: 0 / 10
• Subtask 3: 0 / 5
• Subtask 4: 0 / 56
• Subtask 5: 0 / 20