Submission #1342923

#TimeUsernameProblemLanguageResultExecution timeMemory
1342923ElayV13Toy (CEOI24_toy)C++20
0 / 100
17 ms4080 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

int m,n,k,L;
int xh,yh,xv,yv;
char a[1501][1501];
int p[1501][1501];
bool used[1501][1501];
bool can[1501][1501];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool ok1[1501][1501];
bool ok2[1501][1501];

int get(int x1,int y1,int x2,int y2){
      return p[x2][y2]-p[x2][y1-1]-p[x1-1][y2]+p[x1-1][y1-1];
}

pair<int,int> intersect(int x1,int y1,int x2,int y2){
      return {x1,y2};
}

bool ok(int nwx,int nwy){
      if(nwx<=n&&nwy<=m&&min(nwx,nwy)>=1&&ok1[nwx][nwy]&&ok2[nwx][nwy]&&a[nwx][nwy]!='X'&&!used[nwx][nwy]) return 1;
      return 0;
}

void bfs(int x,int y){
      queue<pair<int,int>>q;
      q.push({x,y});
      used[x][y]=1;
      while(!q.empty()){
            pair<int,int>v=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                  int nwx=v.first+dx[i];
                  int nwy=v.second+dy[i];
                  if(ok(nwx,nwy)){
                        used[nwx][nwy]=1;
                        q.push({nwx,nwy});
                  }
            }
      }
}

void solve(){
      cin>>m>>n>>k>>L;
      cin>>xh>>yh>>xv>>yv;
      ++xh;
      ++yh;
      ++xv;
      ++yv;
      swap(xh,yh);
      swap(xv,yv);
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  cin>>a[i][j];
            }
      }
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  p[i][j]=p[i-1][j]+p[i][j-1]-p[i-1][j-1]+(a[i][j]=='X');
            }
      }
      pair<int,int>point=intersect(xh,yh,xv,yv);
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  if(a[i][j]=='X') continue;
                  int l=1,r=m-j+1,mx1=0,mx2=0;
                  while(l<=r){
                        int mid=(l+r)>>1;
                        if(!get(i,j,i,j+mid-1)){
                              mx1=max(mx1,mid);
                              l=mid+1;
                        }
                        else r=mid-1;
                  }
                  l=1,r=j;
                  while(l<=r){
                        int mid=(l+r)>>1;
                        if(!get(i,j-mid+1,i,j)){
                              mx2=max(mx2,mid);
                              l=mid+1;
                        }
                        else r=mid-1;
                  }
                  if(mx1+mx2-1>=k) ok1[i][j]=1;
            }
      }
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  if(a[i][j]=='X') continue;
                  int l=1,r=n-i+1,mx1=0,mx2=0;
                  while(l<=r){
                        int mid=(l+r)>>1;
                        if(!get(i,j,i+mid-1,j)){
                              mx1=max(mx1,mid);
                              l=mid+1;
                        }
                        else r=mid-1;
                  }
                  l=1,r=i;
                  while(l<=r){
                        int mid=(l+r)>>1;
                        if(!get(i-mid+1,j,i,j)){
                              mx2=max(mx2,mid);
                              l=mid+1;
                        }
                        else r=mid-1;
                  }
                  if(mx1+mx2-1>=L) ok2[i][j]=1;
            }
      }
      bfs(point.first,point.second);
      int xu=-1,yu=-1;
      for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                  if(a[i][j]=='*'){
                        xu=i;
                        yu=j;
                  }
            }
      }
      cout<<((used[xu][yu])?"YES":"NO")<<endl;
}
signed main(){
      ios_base::sync_with_stdio(0);
      cin.tie(0);
      cout.tie(0);
      int T=1;//cin>>T;
      while(T--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...