結果

問題 No.440 2次元チワワ問題
ユーザー 🍡yurahuna🍡yurahuna
提出日時 2016-04-26 19:11:26
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,991 bytes
コンパイル時間 1,399 ms
コンパイル使用メモリ 174,748 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-04 15:56:07
合計ジャッジ時間 2,212 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
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 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);
    }

};

vector<ll> in(string line) {
    stringstream ss(line);

    ll x;
    vector<ll> ret;
    while (ss >> x) {
        ret.emplace_back(x);
    }
    return ret;
}

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

    string line;
    getline(cin, line);
    auto vec = in(line);
    assert(vec.size() == 2);
    ll H = vec[0], W = vec[1];
    assert(1 <= H && H <= 500);
    assert(1 <= W && W <= 500);

    vector<string> s(H);
    rep(i, H) {
        cin >> s[i];
        assert(s[i].size() == W);
        rep(j, W) {
            assert(s[i][j] == 'c' || s[i][j] == 'w');
        }
    }

    // getline(cin, line);
    // vec = in(line);
    // assert(vec.size() == 1);
    // ll Q = vec[0];

    ll Q;
    cin >> Q;
    assert(1 <= Q && Q <= 10000);

    rep(q, Q) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        assert(1 <= a && a <= H);
        assert(1 <= b && b <= W);
        assert(1 <= c && c <= H);
        assert(1 <= d && d <= W);
        assert(a <= c && b <= d);
    }

}
0