結果

問題 No.440 2次元チワワ問題
コンテスト
ユーザー pekempey
提出日時 2016-10-29 04:49:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 68 ms / 5,000 ms
コード長 1,892 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 160,696 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2024-11-24 07:09:30
合計ジャッジ時間 3,523 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:61:20: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
   61 |         printf("%lld\n", s1.solve(x1, x2, y1, y2) + s2.solve(y1, y2, x1, x2));
      |                 ~~~^     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                    |                              |
      |                    long long int                  int64_t {aka long int}
      |                 %ld
main.cpp:52:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |         scanf("%s", buf);
      |         ~~~~~^~~~~~~~~~~
main.cpp:60:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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