Submission #527529

#	Time	Username	Problem	Language	Result	Execution time	Memory
527529		eecs	Sandcastle 2 (JOI22_ho_t5)	C++17	100 / 100	469 ms	35920 KiB

Main

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

const int maxn = 52000;
const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
int h, w, ans, a[maxn], sa[maxn], sb[maxn], cnt[maxn];
int num[9][9][maxn], tmp[9][6][maxn], res[6][6][maxn], pre[6][maxn];

int id(int x, int y) {
    return (x - 1) * w + y;
}

int main() {
    scanf("%d %d", &h, &w);
    int _h = h, _w = w;
    if (h < w) swap(h, w);
    for (int i = 1; i <= _h; i++) {
        for (int j = 1; j <= _w; j++) {
            scanf("%d", &a[_h < _w ? id(j, i) : id(i, j)]);
        }
    }
    for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
        for (int lx : {i - 2, i - 1, i}) for (int rx : {i, i + 1, i + 2}) {
            for (int ly : {j - 2, j - 1, j}) for (int ry : {j, j + 1, j + 2}) {
                if (lx < 0 || rx > h || ly < 0 || ry > w) continue;
                int d = 0;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x < lx || x > rx || y < ly || y > ry) continue;
                    int mx = -1, foo = 0, bar;
                    for (int _k = 0; _k < 4; _k++) {
                        int p = x + dx[_k], q = y + dy[_k];
                        if (p < lx || p > rx || q < ly || q > ry) continue;
                        if (a[id(p, q)] < a[id(x, y)] && a[id(p, q)] > mx) mx = a[id(p, q)], foo = p, bar = q;
                    }
                    if (foo == i && bar == j) { d = 1; break; }
                }
                if (!d) num[(i - lx) * 3 + rx - i][(j - ly) * 3 + ry - j][id(i, j)]++;
            }
        }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 1; j <= h * w; j++) {
            tmp[i][0][j] = num[i][0][j];
            tmp[i][1][j] = num[i][1][j] + num[i][3][j + 1];
            tmp[i][2][j] = num[i][2][j] + num[i][4][j + 1] + num[i][6][j + 2];
            tmp[i][3][j] = num[i][2][j] + num[i][5][j + 1];
            tmp[i][4][j] = num[i][7][j] + num[i][6][j + 1];
            tmp[i][5][j] = num[i][8][j];
        }
    }
    for (int i = 0; i < 6; i++) {
        for (int j = 1; j <= h * w; j++) {
            res[0][i][j] = tmp[0][i][j];
            res[1][i][j] = tmp[1][i][j] + tmp[3][i][j + w];
            res[2][i][j] = tmp[2][i][j] + tmp[4][i][j + w] + tmp[6][i][j + 2 * w];
            res[3][i][j] = tmp[2][i][j] + tmp[5][i][j + w];
            res[4][i][j] = tmp[7][i][j] + tmp[6][i][j + w];
            res[5][i][j] = tmp[8][i][j];
        }
    }
    for (int i = 0; i < 6; i++) {
        for (int j = 1; j <= h * w; j++) {
            pre[i][j] = pre[i][j - 1] + res[i][5][j];
        }
    }
    auto calc = [&](int k, int x, int ly, int ry) {
        if (ry <= ly + 2) return res[k][ry - ly][id(x, ly)];
        if (ry == ly + 3) return res[k][3][id(x, ly)] + res[k][4][id(x, ly + 2)];
        int t = res[k][3][id(x, ly)] + res[k][4][id(x, ry - 1)];
        return t + pre[k][id(x, ry - 2)] - pre[k][id(x, ly + 1)];
    };
    for (int ly = 1; ly <= w; ly++) {
        for (int ry = ly; ry <= w; ry++) {
            fill(sa, sa + h + 1, 0), fill(sb, sb + h + 1, 0);
            for (int i = 1, v8 = 0; i < h; i++) {
                if (i > 2) sa[i - 2] += v8, sb[i + 1] += v8;
                sa[i] -= calc(3, i, ly, ry);
                sb[i + 1] += calc(4, i, ly, ry);
                v8 += calc(5, i, ly, ry);
            }
            for (int i = 1; i <= h; i++) {
                if (i > 3) {
                    cnt[sa[i - 3] + 2 * w]++;
                    ans += cnt[sb[i] + 2 * w - 1];
                }
                for (int j = 0; j <= min(i - 1, 2); j++) {
                    if (calc(j, i - j, ly, ry) == 1) ans++;
                }
            }
            for (int i = 4; i <= h; i++) {
                cnt[sa[i - 3] + 2 * w]--;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |             scanf("%d", &a[_h < _w ? id(j, i) : id(i, j)]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:36:41: warning: 'bar' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |                     if (foo == i && bar == j) { d = 1; break; }
      |                                     ~~~~^~~~

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