結果

問題 No.440 2次元チワワ問題
ユーザー 🍡yurahuna
提出日時 2016-04-26 19:22:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,071 ms / 5,000 ms
コード長 4,924 bytes
コンパイル時間 2,166 ms
コンパイル使用メモリ 183,652 KB
実行使用メモリ 84,608 KB
最終ジャッジ日時 2024-12-17 18:46:55
合計ジャッジ時間 17,670 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

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 all(a) (a).begin(),(a).end()

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

// 想定解
// O(H W + Q(H + W))

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

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

public:

    /*********** 値の設定と前処理 *************/
    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 の個数を返す(以下同様)
    ll C(ll l, ll r) {
        return c1[l] - c1[r];
    }

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

    ll CW(ll l, ll 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);
    }

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

    ll CWW(ll l, ll 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);

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

    ll 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(all(rows2[i]));
    }



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

    // rep(i, H) {
    //     cerr << rows1[i] << endl;
    // }
    // cerr << endl;
    //
    // rep(j, W) {
    //     cerr << cols1[j] << endl;
    // }
    // cerr << endl;
    //
    // rep(i, H) {
    //     cerr << rows2[i] << endl;
    // }
    // cerr << endl;
    //
    // rep(j, W) {
    //     cerr << cols2[j] << endl;
    // }
    // cerr << endl;


    vector<Chiwawa> rowChiwa1(H, Chiwawa(""));
    rep(i, H) rowChiwa1[i] = 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]);



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

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