fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
  5. #define FORD(i, a, b) for(int i = (a); i >= (b); --i)
  6. #define sz(a) (int)(a).size()
  7. #define all(a) (a).begin(), (a).end()
  8. #define bit(s, i) (((s) >> (i)) & 1)
  9. #define ii pair <int, int>
  10. #define fi first
  11. #define se second
  12. #define ll long long
  13. #define int long long
  14. #define eb emplace_back
  15. #define pb push_back
  16. #define __builtin_popcount __builtin_popcountll
  17.  
  18. template <class X, class Y>
  19.     bool maxi(X &x, Y y) {
  20.         if(x < y) {
  21.             x = y;
  22.             return true;
  23.         }
  24.         return false;
  25.     }
  26.  
  27. template <class X, class Y>
  28.     bool mini(X &x, Y y) {
  29.         if(x > y) {
  30.             x = y;
  31.             return true;
  32.         }
  33.         return false;
  34.     }
  35.  
  36. void solve();
  37. int32_t main() {
  38.     #define task "test"
  39.     if(fopen(task".inp", "r")){
  40.         freopen(task".inp", "r", stdin);
  41.         freopen(task".out", "w", stdout);
  42.     }
  43.     cin.tie(0)->sync_with_stdio(0);
  44.  
  45.     int tc = 1; //cin >> tc;
  46.     FOR(i, 1, tc){
  47.         solve();
  48.     }
  49. }
  50.  
  51. const int N=1e3+5;
  52. const int Q=1e6+5;
  53.  
  54. int n,m,q; bool ans[Q];
  55. char a[N][N];
  56. bitset<N> bs1[N][N],bs2[N][N];
  57. ii p1[Q],p2[Q];
  58.  
  59. void dnc(int l, int r, vector<int> p){
  60.     if(l>r || sz(p)==0) return;
  61.  
  62.     int mid=(l+r)>>1;
  63.  
  64.     FOR(i,l-1,mid+1) FOR(j,0,m+1) bs1[i][j]=0;
  65.     FOR(i,mid-1,r+1) FOR(j,0,m+1) bs2[i][j]=0;
  66.     FORD(i,m,1){
  67.         if(a[mid][i]=='.'){
  68.             bs1[mid][i][i]=1;
  69.             bs1[mid][i]|=bs1[mid][i+1];
  70.         }
  71.     }
  72.     FORD(i,mid-1,l){
  73.         FORD(j,m,1) if(a[i][j]=='.'){
  74.             bs1[i][j]=bs1[i+1][j]|bs1[i][j+1];
  75.         }
  76.     }
  77.  
  78.     FOR(i,1,m){
  79.         if(a[mid][i]=='.'){
  80.             bs2[mid][i][i]=1;
  81.             bs2[mid][i]|=bs2[mid][i-1];
  82.         }
  83.     }
  84.     FOR(i,mid+1,r){
  85.         FOR(j,1,m) if(a[i][j]=='.'){
  86.             bs2[i][j]=bs2[i][j-1]|bs2[i-1][j];
  87.         }
  88.     }
  89.  
  90.     vector<int> lt,rt;
  91.     for(int i:p){
  92.         if(p2[i].fi<mid){
  93.             lt.eb(i);
  94.         }
  95.         else if(p1[i].fi>mid){
  96.             rt.eb(i);
  97.         }
  98.         else{
  99.             ans[i]=(bs1[p1[i].fi][p1[i].se]&bs2[p2[i].fi][p2[i].se]).any();
  100.         }
  101.     }
  102.  
  103.     dnc(l,mid-1,lt);
  104.     dnc(mid+1,r,rt);
  105. }
  106.  
  107. void solve() {
  108.     cin>>n>>m>>q;
  109.     FOR(i,1,n) FOR(j,1,m) cin>>a[i][j];
  110.     FOR(i,1,q) cin>>p1[i].fi>>p1[i].se>>p2[i].fi>>p2[i].se;
  111.  
  112.     vector<int> p;
  113.     FOR(i,1,q){
  114.         if(p1[i].fi<=p2[i].fi&&p1[i].se<=p2[i].se) p.eb(i);
  115.     }
  116.  
  117.     dnc(1,n,p);
  118.     FOR(i,1,q) cout<<(ans[i]?"YES\n":"NO\n");
  119. }
  120.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bgrIzD
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!