結果

問題 No.440 2次元チワワ問題
ユーザー 🍡yurahuna🍡yurahuna
提出日時 2016-04-28 09:36:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,506 bytes
コンパイル時間 1,939 ms
コンパイル使用メモリ 182,992 KB
実行使用メモリ 45,568 KB
最終ジャッジ日時 2024-04-15 04:37:54
合計ジャッジ時間 11,996 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 31 ms
9,472 KB
testcase_08 AC 96 ms
9,344 KB
testcase_09 AC 280 ms
23,040 KB
testcase_10 AC 28 ms
9,216 KB
testcase_11 AC 34 ms
6,940 KB
testcase_12 AC 52 ms
15,360 KB
testcase_13 AC 345 ms
30,976 KB
testcase_14 AC 6 ms
6,940 KB
testcase_15 WA -
testcase_16 AC 18 ms
6,940 KB
testcase_17 WA -
testcase_18 AC 639 ms
45,440 KB
testcase_19 AC 618 ms
45,440 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 1,312 ms
45,568 KB
testcase_23 AC 1,324 ms
45,568 KB
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define aint(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> P;

// 想定解
// O(H W + Q(H + W))
// ll を int に換えた

int nC2(int n) {
    return n * (n - 1) / 2;
}

class Chiwawa {
private:
    int N;           // 文字列の長さ
    string s;       // 文字列
    vector<int> c1;  // ！！後ろから！！ [l, N)
    vector<int> c2;  // 前から [0, r)
    vector<int> w1;
    vector<int> w2;
    vector<int> cw1;
    vector<int> cw2;
    vector<int> ww1;
    vector<int> ww2;
    vector<int> cww1;
    vector<int> cww2;

public:

    Chiwawa();

    /*********** 値の設定と前処理 *************/
    Chiwawa(string str) {
        N = str.size();
        s = str;
        if (s == "") return;

        c1.resize(N + 1, 0);
        c2.resize(N + 1, 0);
        w1.resize(N + 1, 0);
        w2.resize(N + 1, 0);
        cw1.resize(N + 1, 0);
        cw2.resize(N + 1, 0);
        ww1.resize(N + 1, 0);
        ww2.resize(N + 1, 0);
        cww1.resize(N + 1, 0);
        cww2.resize(N + 1, 0);

        // 後ろから累積和
        rrep(i, N) {
            if (s[i] == 'c') {
                c1[i]++;
                cw1[i] += w1[i + 1];
                cww1[i] += ww1[i + 1];
            } else {
                w1[i]++;
                ww1[i] += w1[i + 1];
            }

            c1[i] += c1[i + 1];
            w1[i] += w1[i + 1];
            cw1[i] += cw1[i + 1];
            ww1[i] += ww1[i + 1];
            cww1[i] += cww1[i + 1];
        }

        // 前から累積和
        rep2(i, 1, N + 1) {
            if (s[i - 1] == 'w') {
                w2[i]++;
                cw2[i] += c2[i - 1];
                cww2[i] += cw2[i - 1];
                ww2[i] += w2[i - 1];
            } else {
                c2[i]++;
            }
            c2[i] += c2[i - 1];
            w2[i] += w2[i - 1];
            cw2[i] += cw2[i - 1];
            ww2[i] += ww2[i - 1];
            cww2[i] += cww2[i - 1];
        }
    }

    // [l, r) に含まれる c の個数を返す(以下同様)
    int C(int l, int r) {
        return c1[l] - c1[r];
    }

    int W(int l, int r) {
        return w1[l] - w1[r];
    }

    int CW(int l, int r) {
        if (r == N) return cw1[l];
        if (l == 0) return cw2[r];
        return CW(0, N) - CW(0, l) - CW(r, N) - C(0, l) * W(l, N) - C(l, r) * W(r, N);
    }

    int WW(int l, int r) {
        // ww[l, r) = w[l, r) から2個選ぶ方法の数
        return nC2(W(l, r));
    }

    int CWW(int l, int r) {
        if (r == N) return cww1[l];
        if (l == 0) return cww2[r];
        return CWW(0, N) - CWW(0, l) - CWW(r, N) - C(0, l) * (WW(l, r) + WW(r, N)) - C(l, r) * WW(r, N)
                - CW(0, l) * (W(l, r) + W(r, N)) - CW(l, r) * W(r, N) - C(0, l) * W(l, r) * W(r, N);
    }

};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    /*************** 入力 *****************/

    int H, W;
    cin >> H >> W;
    vector<string> rows1(H, "");    // もとの向き
    vector<string> rows2(H, "");    // 逆向き
    vector<string> cols1(W, "");
    vector<string> cols2(W, "");

    rep(i, H) {
        cin >> rows1[i];
        rep(j, W) {
            cols1[j] += rows1[i][j];
        }
    }

    rep(i, H) {
        rows2[i] = rows1[i];
        reverse(aint(rows2[i]));
    }

    rep(j, W) {
        cols2[j] = cols1[j];
        reverse(aint(cols2[j]));
    }

    vector<Chiwawa> rowChiwa1;
    rep(i, H) rowChiwa1.emplace_back(Chiwawa(rows1[i]));

    vector<Chiwawa> rowChiwa2(H, Chiwawa(""));
    rep(i, H) rowChiwa2[i] = Chiwawa(rows2[i]);

    vector<Chiwawa> colChiwa1(W, Chiwawa(""));
    rep(j, W) colChiwa1[j] = Chiwawa(cols1[j]);

    vector<Chiwawa> colChiwa2(W, Chiwawa(""));
    rep(j, W) colChiwa2[j] = Chiwawa(cols2[j]);

    /*********** クエリへの応答 *************/

    int Q;
    cin >> Q;
    rep(q, Q) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--;
        int ans = 0;
        rep2(i, a, c) {
            ans += rowChiwa1[i].CWW(b, d);
            ans += rowChiwa2[i].CWW(W - d, W - b);
        }
        rep2(j, b, d) {
            ans += colChiwa1[j].CWW(a, c);
            ans += colChiwa2[j].CWW(H - c, H - a);
        }
        cout << ans << endl;
    }
}
0