結果
| 問題 | No.3806 Crossword Key with Cropping (Easy) |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-11-14 17:00:42 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 56 ms / 2,000 ms |
| + 577µs | |
| コード長 | 8,228 bytes |
| 記録 | |
| コンパイル時間 | 2,632 ms |
| コンパイル使用メモリ | 359,076 KB |
| 実行使用メモリ | 9,904 KB |
| 最終ジャッジ日時 | 2026-11-14 17:00:51 |
| 合計ジャッジ時間 | 8,757 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 53 |
ソースコード
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
/**
* @file cumulative_sum_2d.hpp
* @brief 二次元累積和
* @author kwm_t
* @see https://github.com/kwm-t/cp-library/blob/main/utility/cumulative_sum_2d.hpp
*/
#ifndef KWM_T_UTILITY_CUMULATIVE_SUM_2D_HPP
#define KWM_T_UTILITY_CUMULATIVE_SUM_2D_HPP
#include <vector>
#include <cassert>
namespace kwm_t::utility {
/**
* @brief 2次元累積和（2D Prefix Sum）
*
* 典型用途:
* - グリッド上の長方形領域の総和を高速に求める
* - 「部分矩形和クエリ」を大量に処理する問題
* - imos法や二次元DPの前処理
*
* 計算量:
* - 構築: O(HW)
* - クエリ: O(1)
*
* @tparam T
* 加算・減算が定義されている型（int, long long, double など）
*
* @param a
* 元となる H×W の2次元配列
*
* 制約 / 注意:
* - 内部的に (H+1)×(W+1) の配列を持つ
* - sum(x0, y0, x1, y1) は半開区間 [x0, x1) × [y0, y1)
* - 0-indexed を前提とする
* - a は長方形（各行のサイズが同じ）であること
*
* 使用例:
* std::vector<std::vector<int>> a = {
* {1, 2, 3},
* {4, 5, 6},
* {7, 8, 9}
* };
*
* kwm_t::utility::CumulativeSum2D<int> cs(a);
*
* // (0,0) から (2,2) の和 → 1+2+4+5 = 12
* int res = cs.sum(0, 0, 2, 2);
*
* verified:
* - https://atcoder.jp/contests/awc0048/submissions/74980601
*/
template <class T>
struct CumulativeSum2D {
private:
std::vector<std::vector<T>> s;
void build(const std::vector<std::vector<T>>& a) {
int h = a.size();
int w = h ? a[0].size() : 0;
s.assign(h + 1, std::vector<T>(w + 1, T{}));
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
s[i + 1][j + 1] = a[i][j];
for (int i = 0; i <= h; i++)
for (int j = 0; j < w; j++)
s[i][j + 1] += s[i][j];
for (int i = 0; i < h; i++)
for (int j = 0; j <= w; j++)
s[i + 1][j] += s[i][j];
}
public:
CumulativeSum2D() = default;
explicit CumulativeSum2D(const std::vector<std::vector<T>>& a) {
build(a);
}
int height() const { return (int)s.size() - 1; }
int width() const { return s.empty() ? 0 : (int)s[0].size() - 1; }
// [x0, x1) × [y0, y1)
T sum(int x0, int y0, int x1, int y1) const {
assert(0 <= x0 && x0 <= x1 && x1 <= height());
assert(0 <= y0 && y0 <= y1 && y1 <= width());
return s[x1][y1]
- s[x1][y0]
- s[x0][y1]
+ s[x0][y0];
}
};
} // namespace kwm_t::utility
#endif // KWM_T_UTILITY_CUMULATIVE_SUM_2D_HPP
vector<P> key_list(std::vector<string>s, int mode = 0) {
int h = s.size();
int w = s[0].size();
auto keyData = [&](int i, int j)->P {
int x = -1, y = -1;
if (s[i][j] == '#')return { x,y };
// 横
if (j != w - 1 && s[i][j + 1] != '#'
&& (j == 0 || s[i][j - 1] == '#')) {
x = 0;
rep2(nj, j, w) {
if (s[i][nj] == '#')break;
x++;
}
}
// 縦
if (i != h - 1 && s[i + 1][j] != '#'
&& (i == 0 || s[i - 1][j] == '#')) {
y = 0;
rep2(ni, i, h) {
if (s[ni][j] == '#')break;
y++;
}
}
if (x == -1 && y == -1) {
bool up = (i == 0 || s[i - 1][j] == '#');
bool down = (i == h - 1 || s[i + 1][j] == '#');
bool left = (j == 0 || s[i][j - 1] == '#');
bool right = (j == w - 1 || s[i][j + 1] == '#');
if (up && down && left && right) {
x = 1;
y = 1;
}
}
return { x,y };
};
vector<P>ret;
rep(i, h)rep(j, w) {
auto key = keyData(i, j);
if (key.first + key.second == -2)continue;
if (mode == 0)ret.emplace_back(i, j);
else ret.push_back(key);
}
return ret;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int h, w; cin >> h >> w;
vector<string>s(h);
rep(i, h)cin >> s[i];
auto keys = key_list(s, 0);
// 内側
vector c(h, vector<int>(w));
for (auto [x, y] : keys)c[x][y]++;
kwm_t::utility::CumulativeSum2D<int> cs(c);
// じっそうめんどうなのでacに方針だけ指示して実装させています
auto calc = [&](int i, int j, bool up, bool down, bool left, bool right)->int {
if (s[i][j] == '#')return 0;
auto blocked = [&](int ni, int nj, bool force) {
return force || ni < 0 || ni >= h || nj < 0 || nj >= w
|| s[ni][nj] == '#';
};
bool u = blocked(i - 1, j, up);
bool d = blocked(i + 1, j, down);
bool l = blocked(i, j - 1, left);
bool r = blocked(i, j + 1, right);
bool horizontal = l && !r;
bool vertical = u && !d;
bool single = u && d && l && r;
return horizontal || vertical || single;
};
// 上下左右の外周用 1D 累積和
vector top(h, vector<int>(w + 1));
vector bottom(h, vector<int>(w + 1));
vector left(w, vector<int>(h + 1));
vector right(w, vector<int>(h + 1));
// 1行・1列用（上下両方・左右両方を強制）
vector bothV(h, vector<int>(w + 1));
vector bothH(w, vector<int>(h + 1));
rep(i, h)rep(j, w) {
top[i][j + 1] = top[i][j] + calc(i, j, 1, 0, 0, 0);
bottom[i][j + 1] = bottom[i][j] + calc(i, j, 0, 1, 0, 0);
bothV[i][j + 1] = bothV[i][j] + calc(i, j, 1, 1, 0, 0);
left[j][i + 1] = left[j][i] + calc(i, j, 0, 0, 1, 0);
right[j][i + 1] = right[j][i] + calc(i, j, 0, 0, 0, 1);
bothH[j][i + 1] = bothH[j][i] + calc(i, j, 0, 0, 1, 1);
}
int q;
cin >> q;
while (q--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a--, b--;
int ans = 0;
int dx = c - a;
int dy = d - b;
// 1マス
if (dx == 1 && dy == 1) {
ans = calc(a, b, 1, 1, 1, 1);
}
// 1行
else if (dx == 1) {
ans += bothV[a][d - 1] - bothV[a][b + 1];
ans += calc(a, b, 1, 1, 1, 0);
ans += calc(a, d - 1, 1, 1, 0, 1);
}
// 1列
else if (dy == 1) {
ans += bothH[b][c - 1] - bothH[b][a + 1];
ans += calc(a, b, 1, 0, 1, 1);
ans += calc(c - 1, b, 0, 1, 1, 1);
}
else {
// 内部
ans += cs.sum(a + 1, b + 1, c - 1, d - 1);
// 上端
ans += top[a][d - 1] - top[a][b + 1];
// 下端
ans += bottom[c - 1][d - 1] - bottom[c - 1][b + 1];
// 左端
ans += left[b][c - 1] - left[b][a + 1];
// 右端
ans += right[d - 1][c - 1] - right[d - 1][a + 1];
// 四隅
ans += calc(a, b, 1, 0, 1, 0);
ans += calc(a, d - 1, 1, 0, 0, 1);
ans += calc(c - 1, b, 0, 1, 1, 0);
ans += calc(c - 1, d - 1, 0, 1, 0, 1);
}
cout << ans << '\n';
}
/*int q; cin >> q;
while (q--) {
int a, b, c, d; cin >> a >> b >> c >> d;
a--, b--;
int dx = c - a;
int dy = d - b;
int ans = 0;
if (dx >= 3 && dy >= 3)ans += cs.sum(a + 1, b + 1, c - 1, d - 1);
// 外周を頑張る
auto f2 = [&](int x, int y)->bool {
if (s[x][y] == '#')return false;
// ue
int cnt = 0;
{
bool chk0 = false;
if (x == a)chk0 = true;
if (x != a && s[x - 1][y] == '#')chk0 = true;
if (chk0) {
int x2 = x + 1, y2 = y;
if (x2 < c && y2 < d && s[x2][y2] != '#')return true;
else cnt++;
}
}
// hidari
{
bool chk0 = false;
if (y == b)chk0 = true;
if (y != b && s[x][y - 1] == '#')chk0 = true;
if (chk0) {
int x2 = x, y2 = y + 1;
if (x2 < c && y2 < d && s[x2][y2] != '#')return true;
else cnt++;
}
}
if (cnt == 2)return true;
return false;
};
if (dx == 1) {
ans = 0;
rep2(j, b, d)ans += f2(a, j);
}
else if (dy == 1) {
ans = 0;
rep2(i, a, c)ans += f2(i, b);
}
else {
rep2(j, b, d - 1)ans += f2(a, j);
rep2(i, a, c - 1)ans += f2(i, d - 1);
rep2(i, a + 1, c)ans += f2(i, b);
rep2(j, b + 1, d)ans += f2(c - 1, j);
}
cout << ans << endl;
}*/
return 0;
}