제출 #1133422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133422		_8_8_	Sandcastle 2 (JOI22_ho_t5)	C++20	71 / 100	5092 ms	40264 KiB

Main

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;

const int  N = (int)5e4 + 12, MOD = 998244353, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}, inf = (int)1e9;

int n, m;
vector<vector<int>> a(N);
vector<vector<vector<ll>>> val(N), dp(N);
void prec() {
    vector<int> c;
    for(int i = 0; i <= n; i++) {
        dp[i].resize(m + 1);
        val[i].resize(m + 1);
        for(int j = 0; j <= m; j++) {
            dp[i][j].resize(16);
            val[i][j].resize(16);
        }
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; j++) {
            c.push_back(a[i][j]);
        }
    }
    sort(c.begin(), c.end());
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            a[i][j] = lower_bound(c.begin(), c.end(), a[i][j]) - c.begin() + 1;
        }
    }
}
ll sum(int x, int y, int x1, int y1, int f) {
    if(x > x1) return 0;
    if(y > y1) return 0;
    return dp[x1][y1][f] - dp[x - 1][y1][f] - dp[x1][y - 1][f] + dp[x - 1][y - 1][f];
}
void test() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        a[i].resize(m + 1);
        for(int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    prec();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int f = 1; f < 16; f++) {
                bool ok = 0;
                int mx = 0;
                for(int d = 0; d < 4; d++) {
                    if((f >> d) & 1) {
                        int x = i + dx[d], y = j + dy[d];
                        if(x >= 1 && x <= n && y >= 1 && y <= m) {
                            if(a[x][y] > a[i][j]) {
                                ok = 1;
                            } else {
                                mx = max(mx, a[x][y]);
                            }
                        }
                    }
                }
                if(ok) {
                    val[i][j][f] = a[i][j] - mx;
                } else {
                    val[i][j][f] = inf - mx;
                }
                dp[i][j][f] = dp[i - 1][j][f] + dp[i][j - 1][f] - dp[i - 1][j - 1][f] + val[i][j][f];
            }
        }
    }
    int res = n * m;
    for(int x = 1; x <= n; x++) {
        for(int y = 1; y <= m; y++) {
            for(int x1 = x; x1 <= n; x1++) {
                for(int y1 = y; y1 <= m; y1++) {
                    if(x == x1 && y == y1) continue;
                    if(x == x1) {
                        ll S = sum(x, y, x, y, 1) + sum(x, y1, x, y1, 4) + sum(x, y + 1, x, y1 - 1, 5);
                        if(S == inf) {
                            res++;
                        }
                        continue;
                    }
                    if(y == y1) {
                        ll S = sum(x, y, x, y, 2) + sum(x1, y1, x1, y1, 8) + sum(x + 1, y, x1 - 1, y, 10);
                        if(S == inf) {
                            res++;
                        }
                        continue;
                    }
                    ll S = sum(x + 1, y + 1, x1 - 1, y1 - 1, 15);
                    S += sum(x, y, x, y, 3);
                    S += sum(x1, y1, x1, y1, 12);
                    S += sum(x1, y, x1, y, 9);
                    S += sum(x, y1, x, y1, 6);
                    S += sum(x, y + 1, x, y1 - 1, 7) + sum(x1, y + 1, x1, y1 - 1, 13);
                    S += sum(x + 1, y, x1 - 1, y, 11) + sum(x + 1, y1, x1 - 1, y1, 14);
                    // cout << S << '\n';
                    if(S == inf) {
                        res++;
                    }
                }
            }
        }
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}   

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