oj.uz

Submission #527918

# Submission time Handle Problem Language Result Execution time Memory
527918 2022-02-18T17:30:40 Z SorahISA Sandcastle 2 (JOI22_ho_t5) C++17
80 / 100
 5000 ms 227648 KB 
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int int64_t
#define double long double
using pii = pair<int, int>;
template <typename T>
using Prior = std::priority_queue<T>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ee emplace
#define eb emplace_back
#define ef push_front
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    cerr << "\u001b[33m" << "At func " << __FUNCTION__ << ", line " << __LINE__ << ": ",\
    cerr << "(" << #__VA_ARGS__ << ") = ",\
    _do(__VA_ARGS__),\
    cerr << "\u001b[0m"
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const int dx[] = {1, 0,-1, 0};
const int dy[] = {0, 1, 0,-1};

void solve() {
    int H, W; cin >> H >> W;
    
    if (H == 1) {
        vector<int> board(W);
        for (int &x : board) cin >> x;
        
        int ans = W;
        for (int i = 1, flag = 0, len = 0; i < W; ++i) {
                 if (flag == 0 and board[i] > board[i-1]) flag = 1, len = 0;
            else if (flag == 1 and board[i] < board[i-1]) flag = 0, len = 0;
            ans += ++len;
        }
        return cout << ans << "\n", void();
    }
    
    vector<vector<int>> board(H+2, vector<int>(W+2, 0));
    for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) cin >> board[i][j];
    
    auto valid = [&](int x, int y) -> bool {
        return 0 <= x and x <= H+1 and 0 <= y and y <= W+1;
    };
    
    auto check = [&](int nx, int ny, int gx, int gy, int l, int r, int d, int u) -> bool {
        /// x-l, x+r, y-d, y+u ///
        if (!(nx-l <= gx and gx <= nx+r and ny-d <= gy and gy <= ny+u)) return false;
        int mx_nei = 0, mx_dir = -1;
        for (int _ : {0, 1, 2, 3}) {
            int tx = gx + dx[_], ty = gy + dy[_];
            if (!(nx-l <= tx and tx <= nx+r and ny-d <= ty and ty <= ny+u)) continue;
            if (valid(tx, ty) and board[tx][ty] < board[gx][gy] and chmax(mx_nei, board[tx][ty])) mx_dir = _;
        }
        // debug(nx, ny, gx, gy, l, r, d, u, mx_dir, gx + dx[mx_dir], gy + dy[mx_dir]);
        return mx_dir != -1 and gx + dx[mx_dir] == nx and gy + dy[mx_dir] == ny;
    };
    
    auto T = [](int l, int r, int d, int u) -> int {
        return 27*l + 9*r + 3*d + 1*u;
    };
    
    vector<vector<vector<int>>> pre(81, vector<vector<int>>(H+2, vector<int>(W+2, 0)));
    
    for (int l : {0, 1, 2}) for (int r : {0, 1, 2}) {
        for (int d : {0, 1, 2}) for (int u : {0, 1, 2}) {
            for (int i = 1; i <= H; ++i) for (int j = 1; j <= W; ++j) {
                int deg_i = 0;
                for (int _ : {0, 1, 2, 3}) deg_i += check(i, j, i+dx[_], j+dy[_], l, r, d, u);
                pre[T(l, r, d, u)][i][j] = deg_i == 0;
            }
        }
    }
    
    for (int k = 0; k < 81; ++k) {
        for (int i = 1; i <= H; ++i) {
            for (int j = 1; j <= W; ++j) {
                pre[k][i][j] += pre[k][i-1][j] + pre[k][i][j-1] - pre[k][i-1][j-1];
            }
        }
    }
    
    auto get = [&](int lay, int x1, int x2, int y1, int y2) -> int {
        if (x1 > x2 or y1 > y2) return 0;
        return pre[lay][x2][y2] - pre[lay][x1-1][y2] - pre[lay][x2][y1-1] + pre[lay][x1-1][y1-1];
    };
    
    int ans = 0;
    for (int x1 = 1; x1 <= H; ++x1) for (int x2 = x1; x2 <= H; ++x2) {
        for (int y1 = 1; y1 <= W; ++y1) for (int y2 = y1; y2 <= W; ++y2) {
            // debug(x1, x2, y1, y2);
            int cnt = 0;
            if (x2-x1+1 <= 3 and y2-y1+1 <= 3) {
                for (int x = x1; x <= x2; ++x) for (int y = y1; y <= y2; ++y) {
                    int deg_i = 0;
                    for (int _ : {0, 1, 2, 3}) deg_i += check(x, y, x+dx[_], y+dy[_], x-x1, x2-x, y-y1, y2-y);
                    // debug(x, y, deg_i);
                    cnt += deg_i == 0;
                }
            }
            else if (x2-x1+1 == 1) {
                cnt += get(T(0, 0, 0, 2), x1, x1, y1, y1) + get(T(0, 0, 1, 2), x1, x1, y1+1, y1+1);
                cnt += get(T(0, 0, 2, 0), x1, x1, y2, y2) + get(T(0, 0, 2, 1), x1, x1, y2-1, y2-1);
                cnt += get(T(0, 0, 2, 2), x1, x1, y1+2, y2-2);
            }
            else if (y2-y1+1 == 1) {
                cnt += get(T(0, 2, 0, 0), x1, x1, y1, y1) + get(T(1, 2, 0, 0), x1+1, x1+1, y1, y1);
                cnt += get(T(2, 0, 0, 0), x2, x2, y1, y1) + get(T(2, 1, 0, 0), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 2, 0, 0), x1+2, x2-2, y1, y1);
            }
            else if (x2-x1+1 == 2) {
                cnt += get(T(0, 1, 0, 2), x1, x1, y1, y1) + get(T(0, 1, 1, 2), x1, x1, y1+1, y1+1);
                cnt += get(T(0, 1, 2, 0), x1, x1, y2, y2) + get(T(0, 1, 2, 1), x1, x1, y2-1, y2-1);
                cnt += get(T(0, 1, 2, 2), x1, x1, y1+2, y2-2);
                cnt += get(T(1, 0, 0, 2), x2, x2, y1, y1) + get(T(1, 0, 1, 2), x2, x2, y1+1, y1+1);
                cnt += get(T(1, 0, 2, 0), x2, x2, y2, y2) + get(T(1, 0, 2, 1), x2, x2, y2-1, y2-1);
                cnt += get(T(1, 0, 2, 2), x2, x2, y1+2, y2-2);
            }
            else if (y2-y1+1 == 2) {
                cnt += get(T(0, 2, 0, 1), x1, x1, y1, y1) + get(T(1, 2, 0, 1), x1+1, x1+1, y1, y1);
                cnt += get(T(2, 0, 0, 1), x2, x2, y1, y1) + get(T(2, 1, 0, 1), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 2, 0, 1), x1+2, x2-2, y1, y1);
                cnt += get(T(0, 2, 1, 0), x1, x1, y2, y2) + get(T(1, 2, 1, 0), x1+1, x1+1, y2, y2);
                cnt += get(T(2, 0, 1, 0), x2, x2, y2, y2) + get(T(2, 1, 1, 0), x2-1, x2-1, y2, y2);
                cnt += get(T(2, 2, 1, 0), x1+2, x2-2, y2, y2);
            }
            else if (x2-x1+1 == 3) {
                int x3 = x1 + 1;
                cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(0, 2, 1, 2), x1, x1, y1+1, y1+1);
                cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(0, 2, 2, 1), x1, x1, y2-1, y2-1);
                cnt += get(T(0, 2, 2, 2), x1, x1, y1+2, y2-2);
                cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 0, 1, 2), x2, x2, y1+1, y1+1);
                cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 0, 2, 1), x2, x2, y2-1, y2-1);
                cnt += get(T(2, 0, 2, 2), x2, x2, y1+2, y2-2);
                cnt += get(T(1, 1, 0, 2), x3, x3, y1, y1) + get(T(1, 1, 1, 2), x3, x3, y1+1, y1+1);
                cnt += get(T(1, 1, 2, 0), x3, x3, y2, y2) + get(T(1, 1, 2, 1), x3, x3, y2-1, y2-1);
                cnt += get(T(1, 1, 2, 2), x3, x3, y1+2, y2-2);
            }
            else if (y2-y1+1 == 3) {
                int y3 = y1 + 1;
                cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(1, 2, 0, 2), x1+1, x1+1, y1, y1);
                cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 1, 0, 2), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 2, 0, 2), x1+2, x2-2, y1, y1);
                cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(1, 2, 2, 0), x1+1, x1+1, y2, y2);
                cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 1, 2, 0), x2-1, x2-1, y2, y2);
                cnt += get(T(2, 2, 2, 0), x1+2, x2-2, y2, y2);
                cnt += get(T(0, 2, 1, 1), x1, x1, y3, y3) + get(T(1, 2, 1, 1), x1+1, x1+1, y3, y3);
                cnt += get(T(2, 0, 1, 1), x2, x2, y3, y3) + get(T(2, 1, 1, 1), x2-1, x2-1, y3, y3);
                cnt += get(T(2, 2, 1, 1), x1+2, x2-2, y3, y3);
            }
            else {
                cnt += get(T(0, 2, 0, 2), x1, x1, y1, y1) + get(T(1, 2, 1, 2), x1+1, x1+1, y1+1, y1+1);
                cnt += get(T(0, 2, 2, 0), x1, x1, y2, y2) + get(T(1, 2, 2, 1), x1+1, x1+1, y2-1, y2-1);
                cnt += get(T(2, 0, 0, 2), x2, x2, y1, y1) + get(T(2, 1, 1, 2), x2-1, x2-1, y1+1, y1+1);
                cnt += get(T(2, 0, 2, 0), x2, x2, y2, y2) + get(T(2, 1, 2, 1), x2-1, x2-1, y2-1, y2-1);
                cnt += get(T(0, 2, 1, 2), x1, x1, y1+1, y1+1) + get(T(1, 2, 0, 2), x1+1, x1+1, y1, y1);
                cnt += get(T(0, 2, 2, 1), x1, x1, y2-1, y2-1) + get(T(1, 2, 2, 0), x1+1, x1+1, y2, y2);
                cnt += get(T(2, 0, 1, 2), x2, x2, y1+1, y1+1) + get(T(2, 1, 0, 2), x2-1, x2-1, y1, y1);
                cnt += get(T(2, 0, 2, 1), x2, x2, y2-1, y2-1) + get(T(2, 1, 2, 0), x2-1, x2-1, y2, y2);
                cnt += get(T(0, 2, 2, 2), x1, x1, y1+2, y2-2) + get(T(1, 2, 2, 2), x1+1, x1+1, y1+2, y2-2);
                cnt += get(T(2, 0, 2, 2), x2, x2, y1+2, y2-2) + get(T(2, 1, 2, 2), x2-1, x2-1, y1+2, y2-2);
                cnt += get(T(2, 2, 0, 2), x1+2, x2-2, y1, y1) + get(T(2, 2, 1, 2), x1+2, x2-2, y1+1, y1+1);
                cnt += get(T(2, 2, 2, 0), x1+2, x2-2, y2, y2) + get(T(2, 2, 2, 1), x1+2, x2-2, y2-1, y2-1);
                cnt += get(T(2, 2, 2, 2), x1+2, x2-2, y1+2, y2-2);
            }
            if (cnt == 1) ++ans;
        }
    }
    cout << ans << "\n";
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 472 KB Output is correct
3 Correct 5 ms 472 KB Output is correct
4 Correct 7 ms 472 KB Output is correct
5 Correct 4 ms 460 KB Output is correct
6 Correct 4 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 33 ms 7124 KB Output is correct
8 Correct 32 ms 7116 KB Output is correct
9 Correct 49 ms 940 KB Output is correct
10 Correct 41 ms 1000 KB Output is correct
11 Correct 27 ms 1288 KB Output is correct
12 Correct 25 ms 3728 KB Output is correct
13 Correct 35 ms 844 KB Output is correct
14 Correct 22 ms 716 KB Output is correct
15 Correct 41 ms 972 KB Output is correct
16 Correct 49 ms 1008 KB Output is correct

Subtask #4
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 33 ms 7124 KB Output is correct
8 Correct 32 ms 7116 KB Output is correct
9 Correct 49 ms 940 KB Output is correct
10 Correct 41 ms 1000 KB Output is correct
11 Correct 27 ms 1288 KB Output is correct
12 Correct 25 ms 3728 KB Output is correct
13 Correct 35 ms 844 KB Output is correct
14 Correct 22 ms 716 KB Output is correct
15 Correct 41 ms 972 KB Output is correct
16 Correct 49 ms 1008 KB Output is correct
17 Correct 495 ms 32460 KB Output is correct
18 Correct 794 ms 3096 KB Output is correct
19 Correct 683 ms 2996 KB Output is correct
20 Correct 698 ms 2872 KB Output is correct
21 Correct 666 ms 2904 KB Output is correct
22 Correct 675 ms 2948 KB Output is correct
23 Correct 651 ms 2864 KB Output is correct
24 Correct 613 ms 2652 KB Output is correct
25 Correct 700 ms 2932 KB Output is correct
26 Correct 775 ms 2892 KB Output is correct
27 Correct 717 ms 2928 KB Output is correct
28 Correct 707 ms 2892 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 33 ms 7124 KB Output is correct
8 Correct 32 ms 7116 KB Output is correct
9 Correct 49 ms 940 KB Output is correct
10 Correct 41 ms 1000 KB Output is correct
11 Correct 27 ms 1288 KB Output is correct
12 Correct 25 ms 3728 KB Output is correct
13 Correct 35 ms 844 KB Output is correct
14 Correct 22 ms 716 KB Output is correct
15 Correct 41 ms 972 KB Output is correct
16 Correct 49 ms 1008 KB Output is correct
17 Correct 495 ms 32460 KB Output is correct
18 Correct 794 ms 3096 KB Output is correct
19 Correct 683 ms 2996 KB Output is correct
20 Correct 698 ms 2872 KB Output is correct
21 Correct 666 ms 2904 KB Output is correct
22 Correct 675 ms 2948 KB Output is correct
23 Correct 651 ms 2864 KB Output is correct
24 Correct 613 ms 2652 KB Output is correct
25 Correct 700 ms 2932 KB Output is correct
26 Correct 775 ms 2892 KB Output is correct
27 Correct 717 ms 2928 KB Output is correct
28 Correct 707 ms 2892 KB Output is correct
29 Execution timed out 5085 ms 227648 KB Time limit exceeded
30 Halted 0 ms 0 KB -