Submission #1183322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183322		jerzyk	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	756 ms	32504 KiB

Main

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 1'000'000'000;
const ll M = 1000'000'007LL;
const int N = 50'007;
const int K = 200'007;
int n, m;
int tab[N];
int il[9][9][N], sum[9][9][N];
vector<pair<int, int>> roza = {make_pair(-1, 0), make_pair(0, -1), make_pair(1, 0), make_pair(0, 1)};
int pre[3 * K], val[N];

inline int G(int i, int j)
{
    if(i == 0 || j == 0 || i == n + 1 || j == m + 1) return 0;
    return (i - 1) * m + j;
}

inline void Cnt(int i, int j)
{
    //cout << "Cnt: " << i << " " << j << "\n";
    for(int ix = 0; ix < 9; ++ix)
        for(int iy = 0; iy < 9; ++iy)
        {
            int i1 = i - ix / 3, i2 = i + ix % 3;
            int j1 = j - iy / 3, j2 = j + iy % 3;
            if(i1 < 1 || j1 < 1 || i2 > n || j2 > m) continue;
            int czy = 0, vl = tab[G(i, j)];
            for(int l = 0; l < (int)roza.size(); ++l)
            {
                int ci = i + roza[l].st, cj = j + roza[l].nd;
                if(ci < i1 || ci > i2 || cj < j1 || cj > j2) continue;
                int ma = 0, cr = tab[G(ci, cj)];
                //cout << "S: " << ci << " " << cj << " " << cr << " " << ma << "\n";
                for(int k = 0; k < (int)roza.size(); ++k)
                {
                    int ni = ci + roza[k].st, nj = cj + roza[k].nd;
                    if(ni < i1 || ni > i2 || nj < j1 || nj > j2) continue;
                    int a = tab[G(ni, nj)];
                    //cerr << ni << " " << nj << " " << a << " ";
                    if(a < cr) ma = max(ma, a);
                }
                //cerr << "\n";
                if(ma == vl) {czy = 1; break;}
            }
            //cout << i1 << " " << i2 << " " << j1 << " " << j2 << " " << ix << " " << iy << " " << czy << "\n";
            if(!czy) ++il[ix][iy][G(i, j)];
            sum[ix][iy][G(i, j)] = il[ix][iy][G(i, j)];
        }
}

void DoSum(int n, int m)
{
    for(int ix = 0; ix < 9; ++ix)
        for(int i = 1; i <= n; ++i)
            for(int j = 2; j <= m; ++j)
                sum[ix][8][G(i, j)] += sum[ix][8][G(i, j - 1)];
    for(int iy = 0; iy < 9; ++iy)
        for(int i = 2; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                sum[8][iy][G(i, j)] += sum[8][iy][G(i - 1, j)];
}

inline int SR(int i, int ix, int j1, int j2)
{
    return sum[ix][8][G(i, j2)] - sum[ix][8][G(i, j1 - 1)];
}

inline int SC(int i1, int i2, int j, int iy)
{
    return sum[8][iy][G(i2, j)] - sum[8][iy][G(i1 - 1, j)];
}

inline int S(int i1, int i2, int j1, int j2)
{
    return SR(i2, 8, j1, j2) - SR(i1 - 1, 8, j1, j2);
}

inline int Suma(int i1, int i2, int j1, int j2)
{
    int ans = 0;
    int di, di2, dj;
    int pj = 0;
    //cout << il[8][0][G(4, 1)] << " " << sum[8][0][G(4, 1)] << " " << sum[8][0][G(3, 1)] << " " << SC(4, 4, 1, 0) << "\n";
    for(int r = 0; r < 2; ++r)
    {
        di = min(2, i2 - i1), di2 = min(2, i2 - i1 - 1), dj = min(2, j2 - j1 + r);
        ans += il[di][dj + pj * 3][G(i1, j1)];
        if(i1 != i2)
            ans += il[di * 3][dj + pj * 3][G(i2, j1)];
        if(j1 != j2)
            ans += il[di][dj * 3 + pj][G(i1, j2)];
        if(i1 != i2 && j1 != j2)
            ans += il[di * 3][dj * 3 + pj][G(i2, j2)];
        //cout << "S: " << ans << "\n";
        
        if(i1 + 1 < i2)
            ans += il[di2 + 3][dj + pj * 3][G(i1 + 1, j1)];
        if(i2 - 2 > i1)
            ans += il[di2 * 3 + 1][dj + pj * 3][G(i2 - 1, j1)];
        if(i1 + 1 < i2 && j1 != j2)
            ans += il[di2 + 3][dj * 3 + pj][G(i1 + 1, j2)];
        if(i2 - 2 > i1 && j1 != j2)
            ans += il[di2 * 3 + 1][dj * 3 + pj][G(i2 - 1, j2)];
        //cout << "S: " << ans << "\n";

        if(i1 + 3 < i2)
            ans += SC(i1 + 2, i2 - 2, j1, dj + pj * 3);
        if(i1 + 3 < i2 && j1 != j2)
        ans += SC(i1 + 2, i2 - 2, j2, dj * 3 + pj);
        //cout << "S: " << ans << "\n";

        ++j1; --j2; ++pj;
        if(j1 > j2) return ans;
    }
    di = min(2, i2 - i1), di2 = min(2, i2 - i1 - 1);
    ans += SR(i1, di, j1, j2);
    if(i1 != i2)
        ans += SR(i2, di * 3, j1, j2);

    if(i1 + 1 < i2)
        ans += SR(i1 + 1, di2 + 3, j1, j2);
    if(i2 - 2 > i1)
        ans += SR(i2 - 1, di2 * 3 + 1, j1, j2);
    //cout << "XD\n";
    if(i1 + 3 < i2)
        ans += S(i1 + 2, i2 - 2, j1, j2);
    return ans;
}

inline int Mid(int i1, int i2, int j)
{
    int ans = 0, di = min(2, i2 - i1), di2 = min(2, i2 - i1 - 1);
    ans += SR(i1, di, 1, j);
    if(i2 != i1)
        ans += SR(i2, di * 3, 1, j);
    if(i1 + 1 < i2)
        ans += SR(i1 + 1, di2 + 3, 1, j);
    if(i2 - 2 > i1)
        ans += SR(i2 - 1, di2 * 3 + 1, 1, j);

    if(i1 + 3 < i2)
        ans += S(i1 + 2, i2 - 2, 1, j);
    //cout << "M: " << ans << "\n";
    return ans;
}

int CalcBeg(int i1, int i2, int j)
{
    int ans = Mid(i1, i2, j + 1);
    int di = min(2, i2 - i1), di2 = min(2, i2 - i1 - 1);
    for(int r = 0; r < 2; ++r)
    {
        ans -= il[di][2 + r * 3][G(i1, j)];
        if(i1 != i2)
            ans -= il[di * 3][2 + r * 3][G(i2, j)];
        if(i1 + 1 < i2)
            ans -= il[di2 + 3][2 + r * 3][G(i1 + 1, j)];
        if(i2 - 2 > i1)
            ans -= il[di2 * 3 + 1][2 + r * 3][G(i2 - 1, j)];
        if(i1 + 3 < i2)
            ans -= SC(i1 + 2, i2 - 2, j, 2 + r * 3);
        ++j;
    }
    return ans;
}

int CalcEnd(int i1, int i2, int j)
{
    int ans = 0;
    if(j > 2)
        ans += Mid(i1, i2, j - 2);
    int di = min(2, i2 - i1), di2 = min(2, i2 - i1 - 1);
    for(int r = 0; r < 2; ++r)
    {
        ans += il[di][6 + r][G(i1, j)];
        if(i1 != i2)
            ans += il[di * 3][6 + r][G(i2, j)];
        if(i1 + 1 < i2)
            ans += il[di2 + 3][6 + r][G(i1 + 1, j)];
        if(i2 - 2 > i1)
            ans += il[di2 * 3 + 1][6 + r][G(i2 - 1, j)];
        if(i1 + 3 < i2)
            ans += SC(i1 + 2, i2 - 2, j, 6 + r);
        --j;
    }
    return ans;
}

inline int Check(int i1, int i2, int j1, int j2)
{
    return (Suma(i1, i2, j1, j2) == 1);
}

void Solve()
{
    int x;
    cin >> n >> m;
    tab[0] = II;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            cin >> x;
            if(n <= m)
                tab[(i - 1) * m + j] = x;
            else
                tab[(j - 1) * n + i] = x;
        }
    if(n > m) swap(n, m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            Cnt(i, j);
    DoSum(n, m);
    //Cp(4, 9, 4, 9);
    //cout << il[3][5][G(2, 2)] << "\n";
    int answer = 0;
    for(int i1 = 1; i1 <= n; ++i1)
        for(int i2 = i1; i2 <= n; ++i2)
            for(int j1 = 1; j1 <= m; ++j1)
                for(int j2 = j1; j2 <= j1 + 2; ++j2)
                {
                    int d = Check(i1, i2, j1, j2);
                    answer += d;
                }
    for(int i1 = 1; i1 <= n; ++i1)
        for(int i2 = i1; i2 <= n; ++i2)
        {
            for(int j = 1; j <= m - 3; ++j)
                val[j] = CalcBeg(i1, i2, j) + K;
            for(int j = 4; j <= m; ++j)
            {
                ++pre[val[j - 3]];
                int a = CalcEnd(i1, i2, j);
                //int d = pre[K + a - 1];
                //cout << i1 << " " << i2 << " " << j << " " << d << " a: " << a << " " << val[1] - K << " " << val[2] - K << "\n";
                answer += pre[K + a - 1];
            }
            for(int j = 1; j <= m - 3; ++j)
                --pre[val[j]];
        }
    cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

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