結果

問題 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0