結果
| 問題 | No.3806 Crossword Key with Cropping (Easy) |
| ユーザー |
 ふらわぁ
|
| 提出日時 | 2026-10-25 00:44:50 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 6,112 bytes |
| 記録 | |
| コンパイル時間 | 5,087 ms |
| コンパイル使用メモリ | 400,416 KB |
| 実行使用メモリ | 9,924 KB |
| 最終ジャッジ日時 | 2026-11-14 14:35:09 |
| 合計ジャッジ時間 | 23,365 ms |
|
ジャッジサーバーID （参考情報） |
judge5_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 7 WA * 46 |
コンパイルメッセージ
main.cpp:73:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
73 | #pragma once
| ^~~~
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#ifdef _MSC_VER
#include <intrin.h>
#endif
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using P = pair<ll, ll>;
//#define endl "\n"
#define rep1(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define OVERLOAD_REP(_1, _2, _3, name, ...) name
#define rep(...) OVERLOAD_REP(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define rrep(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define all(s) (s).begin(), (s).end()
#define fi first
#define se second
const ll mod = 998244353;
const ll inf = 4000000000000000000ll;
const ld eps = ld(0.00000000001);
static const long double pi = 3.141592653589793;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>auto min(const T& a){ return *min_element(all(a)); }
template<class T>auto max(const T& a){ return *max_element(all(a)); }
template<class T,class U>bool chmax(T &a,const U b) { if (a<b) { a=b; return 1; } return 0;}
template<class T,class U>bool chmin(T &a,const U b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t<u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<V<V<T>>>;
template <class T>
auto mvec(T val, ll n) { return V<T>(n, val); }
template <class T, class... Args>
auto mvec(T val, ll n, Args... args) {
return V<decltype(mvec(val, args...))>(n, mvec(val, args...));
}
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / i);}}}sort(all(ans)); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}
void cincout(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout<< fixed << setprecision(15);
}
#pragma once
template <typename T, typename F>
struct SegmentTree2D {
private:
int id(int h, int w) const { return h * 2 * W + w; }
public:
int H, W;
vector<T> seg;
const F f;
const T I;
SegmentTree2D(int h, int w, F _f, const T& i) : f(_f), I(i) { init(h, w); }
void init(int h, int w) {
H = W = 1;
while (H < h) H <<= 1;
while (W < w) W <<= 1;
seg.assign(4 * H * W, I);
}
// build にのみ呼ぶ
void set(int h, int w, const T& x) { seg[id(h + H, w + W)] = x; }
void build() {
// w in [W, 2W)
for (int w = W; w < 2 * W; w++) {
for (int h = H - 1; h; h--) {
seg[id(h, w)] = f(seg[id(2 * h + 0, w)], seg[id(2 * h + 1, w)]);
}
}
// h in [0, 2H)
for (int h = 0; h < 2 * H; h++) {
for (int w = W - 1; w; w--) {
seg[id(h, w)] = f(seg[id(h, 2 * w + 0)], seg[id(h, 2 * w + 1)]);
}
}
}
T get(int h, int w) const { return seg[id(h + H, w + W)]; }
T operator()(int h, int w) const { return seg[id(h + H, w + W)]; }
void update(int h, int w, const T& x) {
h += H, w += W;
seg[id(h, w)] = x;
for (int i = h >> 1; i; i >>= 1) {
seg[id(i, w)] = f(seg[id(2 * i + 0, w)], seg[id(2 * i + 1, w)]);
}
for (; h; h >>= 1) {
for (int j = w >> 1; j; j >>= 1) {
seg[id(h, j)] = f(seg[id(h, 2 * j + 0)], seg[id(h, 2 * j + 1)]);
}
}
}
T _inner_query(int h, int w1, int w2) {
T res = I;
for (; w1 < w2; w1 >>= 1, w2 >>= 1) {
if (w1 & 1) res = f(res, seg[id(h, w1)]), w1++;
if (w2 & 1) --w2, res = f(res, seg[id(h, w2)]);
}
return res;
}
// [ (h1,w1), (h2,w2) ) 半開
T query(int h1, int w1, int h2, int w2) {
if (h1 >= h2 || w1 >= w2) return I;
T res = I;
h1 += H, h2 += H, w1 += W, w2 += W;
for (; h1 < h2; h1 >>= 1, h2 >>= 1) {
if (h1 & 1) res = f(res, _inner_query(h1, w1, w2)), h1++;
if (h2 & 1) --h2, res = f(res, _inner_query(h2, w1, w2));
}
return res;
}
};
/**
* @brief 二次元セグメント木
* @docs docs/data-structure-2d/2d-segment-tree.md
*/
void solve(){
ll h,w; cin>>h>>w;
V<string> s(h+1);
rep(i,h){
cin>>s[i];
s[i]+="#";
}
rep(i,w+1) s[h]+="#";
SegmentTree2D seg(h+1,w+1,[](int a,int b){return a+b;},0);
rep(i,h){
rep(j,w){
if(s[i][j]=='#') continue;
bool key=false;
if(i==0){
if(s[i+1][j]=='.') key=true;
}
else{
if(s[i-1][j]=='#'&&s[i+1][j]=='.') key=true;
}
if(j==0){
if(s[i][j+1]=='.') key=true;
}
else{
if(s[i][j-1]=='#'&&s[i][j+1]=='.') key=true;
}
if(key) seg.set(i,j,1);
}
}
seg.build();
ll q; cin>>q;
rep(i,q){
ll a,b,c,d; cin>>a>>b>>c>>d;
ll ans=seg.query(a,b,c,d);
if(s[a-1][b-1]=='.') ans++;
rep(i,a,c) if(s[i][b-1]=='.'&&(s[i-1][b-1]=='#'||(s[i][b]=='.'&&b!=d))) ans++;
rep(i,b,d) if(s[a-1][i]=='.'&&(s[a-1][i-1]=='#'||(s[a][i]=='.'&&a!=c))) ans++;
cout<<ans<<endl;
}
}
int main(){
cincout();
ll t; t=1;
//cin >> t;
rep(tt,t){
solve();
}
return 0;
}