結果

問題 No.3806 Crossword Key with Cropping (Easy)
ユーザー ふらわぁ
提出日時 2026-10-25 13:38:49
言語 C++23(gcc16)
(gcc 16.2.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc16.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 6,706 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,195 ms
コンパイル使用メモリ 401,548 KB
実行使用メモリ 9,932 KB
最終ジャッジ日時 2026-11-14 14:35:33
合計ジャッジ時間 24,777 ms
ジャッジサーバーID
（参考情報） 		judge5_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 WA * 49
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:73:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
   73 | #pragma once
      |         ^~~~

ソースコード

diff #
raw source code 

#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+2);
  rep(i,w+2) s[0]+="#";
  rep(i,1,h+1){
    string ss; cin>>ss;
    s[i]+="#";
    s[i]+=ss;
    s[i]+="#";
  }
  rep(i,w+2) s[h+1]+="#";
  //rep(i,h+2) cout<<s[i]<<endl;
  SegmentTree2D seg(h+2,w+2,[](int a,int b){return a+b;},0);
  rep(i,1,h+1){
    rep(j,1,w+1){
      if(s[i][j]=='#') continue;
      bool key=false;
      if(s[i-1][j]=='#'&&s[i+1][j]=='.') key=true;
      if(s[i][j-1]=='#'&&s[i][j+1]=='.') key=true;
      if(s[i-1][j]=='#'&&s[i+1][j]=='#'&&s[i][j-1]=='#'&&s[i][j+1]=='#') key=true;
      if(key) seg.set(i,j,1);
    }
  }
  seg.build();
  //rep(i,1,h+1) rep(j,1,w+1) cout<<seg.query(i,j,i+1,j+1)<<(j==w?"\n":"");
  ll q; cin>>q;
  rep(i,q){
    ll a,b,c,d; cin>>a>>b>>c>>d;
    ll ans=seg.query(a+1,b+1,c,d);
    //cout<<ans<<endl;
    if(s[a][b]=='.') ans++;
    //cout<<ans<<endl;
    if(s[c][b]=='.'&&(s[c][b+1]=='.'||s[c-1][b]=='#')) ans++;
    //cout<<ans<<endl;
    if(s[a][d]=='.'&&(s[a+1][d]=='.'||s[a][d-1]=='#')) ans++;
    //cout<<ans<<endl;
    if(s[c][d]=='.'&&s[c-1][d]=='#'&&s[c][d-1]=='#') ans++;
    //cout<<ans<<endl;
    rep(i,a+1,c){
      if(s[i][b]=='.'&&(s[i][b+1]=='.'||s[i-1][b]=='#')) ans++;
      if(s[i][d]=='.'&&s[i-1][d]=='#'&&(s[i+1][d]=='.'||s[i][d-1]=='#')) ans++;
    }
    //cout<<ans<<endl;
    rep(i,b+1,d){
      if(s[a][i]=='.'&&(s[a+1][i]=='.'||s[a][i-1]=='#')) ans++;
      if(s[c][i]=='.'&&s[c][i-1]=='#'&&(s[c][i+1]=='.'||s[c-1][i]=='#')) ans++;
    }
    cout<<ans<<endl;
  }
}

int main(){
  cincout();
  ll t; t=1;
  //cin >> t;
  rep(tt,t){
    solve();
  }
  return 0;
}
0