結果

問題 No.440 2次元チワワ問題
ユーザー pekempeypekempey
提出日時 2016-10-29 04:49:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 68 ms / 5,000 ms
コード長 1,892 bytes
コンパイル時間 2,076 ms
コンパイル使用メモリ 146,876 KB
実行使用メモリ 13,576 KB
最終ジャッジ日時 2023-08-15 22:13:30
合計ジャッジ時間 3,518 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
13,496 KB
testcase_01 AC 5 ms
13,576 KB
testcase_02 AC 6 ms
13,384 KB
testcase_03 AC 5 ms
13,380 KB
testcase_04 AC 6 ms
13,492 KB
testcase_05 AC 5 ms
13,444 KB
testcase_06 AC 5 ms
13,380 KB
testcase_07 AC 10 ms
13,440 KB
testcase_08 AC 17 ms
13,440 KB
testcase_09 AC 33 ms
13,432 KB
testcase_10 AC 9 ms
13,440 KB
testcase_11 AC 10 ms
13,368 KB
testcase_12 AC 12 ms
13,368 KB
testcase_13 AC 35 ms
13,428 KB
testcase_14 AC 6 ms
13,372 KB
testcase_15 AC 34 ms
13,432 KB
testcase_16 AC 9 ms
13,444 KB
testcase_17 AC 54 ms
13,512 KB
testcase_18 AC 49 ms
13,368 KB
testcase_19 AC 49 ms
13,428 KB
testcase_20 AC 49 ms
13,432 KB
testcase_21 AC 61 ms
13,372 KB
testcase_22 AC 61 ms
13,488 KB
testcase_23 AC 62 ms
13,440 KB
testcase_24 AC 68 ms
13,440 KB
testcase_25 AC 63 ms
13,428 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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

const int N = 500;

struct Solver {
    struct DP { int c__, cw_, cww, _wc, wwc; };
    int H, W;
    DP dp[N + 1][N + 2];
    bitset<N + 1> s[N + 1]; // c:0 w:1

    void build(int H, int W) {
        this->H = H;
        this->W = W;
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                dp[i][j].c__ = dp[i][j - 1].c__ + !s[i][j];
                dp[i][j].cw_ = dp[i][j - 1].cw_ + (s[i][j] ? dp[i][j - 1].c__ : 0);
                dp[i][j].cww = dp[i][j - 1].cww + (s[i][j] ? dp[i][j - 1].cw_ : 0);
            }
            int c = 0;
            for (int j = W; j >= 1; j--) {
                dp[i][j]._wc = dp[i][j + 1]._wc + (s[i][j] ? c : 0);
                dp[i][j].wwc = dp[i][j + 1].wwc + (s[i][j] ? dp[i][j + 1]._wc : 0);
                c += !s[i][j];
            }
        }
    }

    int64_t solve(int l, int r, int y1, int y2) {
        int64_t res = 0;
        for (int i = y1; i <= y2; i++) {
            int c = dp[i][r].c__ - dp[i][l - 1].c__;
            int w = (r - l + 1) - c;
            res += dp[i][r].cww - dp[i][l - 1].cww;
            res += dp[i][l].wwc - dp[i][r + 1].wwc;
            res -= (dp[i][W].c__ - c) * w * (w - 1) / 2;
            res -= w * (dp[i][l - 1].cw_ + dp[i][r + 1]._wc);
        }
        return res;
    }
};

Solver s1, s2;

int main() {
    int h, w, q;
    cin >> h >> w;
    for (int i = 0; i < h; i++) {
        char buf[512];
        scanf("%s", buf);
        for (int j = 0; j < w; j++) s1.s[i + 1][j + 1] = s2.s[j + 1][i + 1] = buf[j] == 'w';
    }
    s1.build(h, w);
    s2.build(w, h);
    cin >> q;
    for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2;
        scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
        printf("%lld\n", s1.solve(x1, x2, y1, y2) + s2.solve(y1, y2, x1, x2));
    }
}
0