Submission #766300

#	Time	Username	Problem	Language	Result	Execution time	Memory
766300		abysmal	Sandcastle 2 (JOI22_ho_t5)	C++14	80 / 100	5058 ms	34348 KiB

Main

#include<iostream>
#include<stdio.h>
#include<stdint.h>
#include<iomanip>
#include<algorithm>
#include<utility>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<deque>
#include<math.h>
#include<assert.h>

using namespace std;

const int64_t INF = (int64_t) 2 * 1e9 + 100;
const int64_t mINF = (int64_t) 1e9 + 5;
const int64_t MOD = 1e9 + 7;
const int nbit = 31;
const int nchar = 26;
const int D = 4;
int dr[D] = {-1, 0, 1, 0};
int dc[D] = {0, 1, 0, -1};

struct Cell
{
    int r;
    int c;

    Cell(int r_, int c_) : r(r_), c(c_) {}
};

struct Solution
{
    int n;
    int m;
    int nmask;
    vector<int> pow;
    vector<vector<int> > g;
    vector<vector<vector<int> > > a;
    vector<vector<vector<int> > > prefix;
    Solution() {}

    void solve()
    {
        cin >> n >> m;

        if(n > m)
        {
            g.resize(m, vector<int>(n, 0));
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    cin >> g[j][i];
                }
            }

            swap(n, m);
        }
        else
        {
            g.resize(n, vector<int>(m, 0));
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    cin >> g[i][j];
                }
            }
        }

        if(n == 1) Sub1();
        else Sub4();
    }

    void Sub1()
    {
        int t = 0;
        int cnt = 1;
        int64_t ans = 0;
        for(int i = 1; i < m; i++)
        {
            int x = 1;
            if(g[0][i] < g[0][i - 1]) x = -1;
            if(t != x && t != 0)
            {
                ans += 1LL * cnt * (cnt - 1) / 2;
                cnt = 1;
            }

            cnt++;
            t = x;
        }

        ans += 1LL * cnt * (cnt - 1) / 2;
        cout << ans + m << "\n";
    }

    void Sub4()
    {
        int k = 3;
        nmask = 81;
        pow.resize(k + 1, 1);
        for(int i = 1; i <= k; i++)
        {
            pow[i] = pow[i - 1] * 3;
        }

        a.resize(nmask, vector<vector<int> >(n + 1, vector<int>(m + 1, 0)));
        for(int mask = 0; mask < nmask; mask++)
        {
            vector<int> c;
            int tmp = mask;
            for(int i = k; i >= 0; i--)
            {
                int d = tmp / pow[i];
                tmp %= pow[i];

                c.push_back(d);
            }
            reverse(c.begin(), c.end());
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    if(!check(c, i, j)) continue;

                    int cnt = 0;
                    for(int t = 0; t < D; t++)
                    {
                        if(c[t] == 0) continue;

                        Cell v(i + dr[t], j + dc[t]);
                        if(g[v.r][v.c] < g[i][j]) continue;

                        int max_ = g[i][j];
                        if(c[t] == 2)
                        {
                            int val = g[v.r + dr[t]][v.c + dc[t]];
                            if(val < g[v.r][v.c]) max_ = max(max_, val);
                        }

                        int nx = t + 1; if(nx == D) nx -= D;
                        int pr = t - 1; if(pr < 0) pr += D;
                        if(c[nx] != 0)
                        {
                            int val = g[v.r + dr[nx]][v.c + dc[nx]];
                            if(val < g[v.r][v.c]) max_ = max(max_, val);
                        }
                        if(c[pr] != 0)
                        {
                            int val = g[v.r + dr[pr]][v.c + dc[pr]];
                            if(val < g[v.r][v.c]) max_ = max(max_, val);
                        }

                        if(max_ == g[i][j]) cnt++;
                    }

                    if(cnt == 0) a[mask][i][j]++;
                }
            }
        }

        prefix.resize(nmask, vector<vector<int> >(n + 1, vector<int>(m + 1, 0)));
        for(int mask = 0; mask < nmask; mask++)
        {
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= m; j++)
                {
                    prefix[mask][i][j] -= prefix[mask][i - 1][j - 1];
                    prefix[mask][i][j] += a[mask][i - 1][j - 1] + prefix[mask][i - 1][j] + prefix[mask][i][j - 1];
                }
            }
        }

        int64_t ans = 0;
        vector<int> cnt(n * m + 5, 0);
        for(int i = 0; i < n; i++)
        {
            for(int r = i; r < n; r++)
            {
                for(int j = 0; j < m; j++)
                {
                    for(int c = j; c <= min(j + k, m - 1); c++)
                    {
                        int sum = Count(i, j, r, c);

                        if(sum == 1) ans++;
                    }
                }

                int mid = 0;
                for(int j = 3; j < m; j++)
                {
                    int right = CalcRight(i, r, j);
                    mid += CalcMid(i, r, j - 2);
                    int left = CalcLeft(i, r, j - 2);

                    ans += cnt[right + mid];
                    if(-left + mid + 1 >= 0) cnt[-left + mid + 1]++;
                }

                mid = 0;
                for(int j = 3; j < m; j++)
                {
                    mid += CalcMid(i, r, j - 2);
                    int left = CalcLeft(i, r, j - 2);

                    if(-left + mid + 1 >= 0) cnt[-left + mid + 1]--;
                }
            }
        }

        cout << ans << "\n";
    }

    int CalcRight(int i, int r, int j)
    {
        int lx = i;
        int rx = r;
        int sum = 0;
        while(lx <= rx)
        {
            int t1 = getMask(i, j - 3, r, j, lx, j);
            int t2 = getMask(i, j - 3, r, j, lx, j - 1);
            int t3 = getMask(i, j - 3, r, j, rx, j);
            int t4 = getMask(i, j - 3, r, j, rx, j - 1);
            if(t1 == t3) sum += prefix[t1][rx + 1][j + 1] - prefix[t1][rx + 1][j] - prefix[t1][lx][j + 1] + prefix[t1][lx][j];
            else sum += a[t1][lx][j] + a[t3][rx][j];
            if(t2 == t4)
            {
                sum += prefix[t2][rx + 1][j] - prefix[t2][rx + 1][j - 1] - prefix[t2][lx][j] + prefix[t2][lx][j - 1];
                break;
            }
            else sum += a[t2][lx][j - 1] + a[t4][rx][j - 1];

            lx++; rx--;
        }

        return sum;
    }

    int CalcMid(int i, int r, int j)
    {
        int lx = i;
        int rx = r;
        int sum = 0;
        while(lx <= rx)
        {
            int t1 = getMask(i, j - 2, r, j + 2, lx, j);
            int t2 = getMask(i, j - 2, r, j + 2, rx, j);

            if(t1 == t2)
            {
                sum += prefix[t1][rx + 1][j + 1] - prefix[t1][rx + 1][j] - prefix[t1][lx][j + 1] + prefix[t1][lx][j];
                break;
            }
            else sum += a[t1][lx][j] + a[t2][rx][j];
            lx++; rx--;
        }

        return sum;
    }

    int CalcLeft(int i, int r, int j)
    {
        int lx = i;
        int rx = r;
        int sum = 0;
        while(lx <= rx)
        {
            int t1 = getMask(i, j - 1, r, j + 2, lx, j);
            int t2 = getMask(i, j - 1, r, j + 2, lx, j - 1);
            int t3 = getMask(i, j - 1, r, j + 2, rx, j);
            int t4 = getMask(i, j - 1, r, j + 2, rx, j - 1);

            if(t1 == t3) sum += prefix[t1][rx + 1][j + 1] - prefix[t1][rx + 1][j] - prefix[t1][lx][j + 1] + prefix[t1][lx][j];
            else sum += a[t1][lx][j] + a[t3][rx][j];

            if(t2 == t4)
            {
                sum += prefix[t2][rx + 1][j] - prefix[t2][rx + 1][j - 1] - prefix[t2][lx][j] + prefix[t2][lx][j - 1];
                break;
            }
            else sum += a[t2][lx][j - 1] + a[t4][rx][j - 1];

            lx++; rx--;
        }

        return sum;
    }

    int Count(int i, int j, int r, int c)
    {
        int lx = i;
        int rx = r;
        int sum = 0;
        while(lx <= rx)
        {
            int ly = j;
            int ry = c;

            while(ly <= ry)
            {
                int t1 = getMask(i, j, r, c, lx, ly);
                int t2 = getMask(i, j, r, c, lx, ry);
                int t3 = getMask(i, j, r, c, rx, ly);
                int t4 = getMask(i, j, r, c, rx, ry);
                if(t3 == t4 && lx != rx) sum += prefix[t3][rx + 1][ry + 1] - prefix[t3][rx + 1][ly] - prefix[t3][rx][ry + 1] + prefix[t3][rx][ly];
                else if(t3 != t4 && lx != rx) sum += a[t3][rx][ly] + a[t4][rx][ry];

                if(t1 == t2)
                {
                    sum += prefix[t1][lx + 1][ry + 1] - prefix[t1][lx + 1][ly] - prefix[t2][lx][ry + 1] + prefix[t2][lx][ly];
                    break;
                }
                else if(t1 != t2) sum += a[t1][lx][ly] + a[t2][lx][ry];
                ly++; ry--;
            }

            lx++; rx--;
        }

        return sum;
    }

    int getMask(int i, int j, int r, int c, int x, int y)
    {
        int u = min(x - i, 2); int d = min(r - x, 2);
        int l = min(y - j, 2); int rt = min(c - y, 2);
        return u * pow[0] + rt * pow[1] + d * pow[2] + l * pow[3];
    }

    bool check(vector<int>& p, int r, int c)
    {
        return 0 <= r - p[0] && r + p[2] < n &&
               0 <= c - p[3] && c + p[1] < m;
    }

    int modadd(int t1, int t2)
    {
        int res = t1 + t2;
        if(res >= MOD) res -= MOD;
        return res;
    }

    int modmul(int t1, int t2)
    {
        int64_t res = 1LL * t1 * t2;
        return res % MOD;
    }

    int Abs(int tmp)
    {
        if(tmp < 0) return -tmp;
        return tmp;
    }

    int64_t MASK(int j)
    {
        return (1LL << j);
    }

    bool BIT(int64_t tmp, int j)
    {
        return (tmp & MASK(j));
    }
};

void __setup()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
}

int main()
{
    __setup();

    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++)
    {
        Solution().solve();
    }
    return 0;
}

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