結果
問題 | No.440 2次元チワワ問題 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}}