Submission #1343004

#TimeUsernameProblemLanguageResultExecution timeMemory
1343004ElayV13Toy (CEOI24_toy)C++20
100 / 100
637 ms93024 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

int m,n,k,LL;
int xh,yh,xv,yv;
char a[1501][1501];
int p[1501][1501];
bool used[1501][1501];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int U[1501][1501];
int D[1501][1501];
int L[1501][1501];
int R[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};
}

int same(int l1,int r1,int l2,int r2){
      int lo=max(l1,l2);
      int ro=min(r1,r2);
      return max(0ll,ro-lo+1);
}

bool can(int x,int y,int i){
      if(i==0){
            int L1=L[x][y],R1=R[x][y];
            int L2=L[x+1][y],R2=R[x+1][y];
            if(same(L1,R1,L2,R2)>=k) return 1;
            else return 0;
      }
      else if(i==1){
            int L1=L[x][y],R1=R[x][y];
            int L2=L[x-1][y],R2=R[x-1][y];
            if(same(L1,R1,L2,R2)>=k) return 1;
            else return 0;
      }
      else if(i==2){
            int L1=D[x][y],R1=U[x][y];
            int L2=D[x][y+1],R2=U[x][y+1];
            if(same(L1,R1,L2,R2)>=LL) return 1;
            else return 0;
      }
      else{
            int L1=D[x][y],R1=U[x][y];
            int L2=D[x][y-1],R2=U[x][y-1];
            if(same(L1,R1,L2,R2)>=LL) return 1;
            else return 0;
      }
}

bool ok(int nwx,int nwy,int i){
      bool f=(nwx<=n&&nwy<=m&&min(nwx,nwy)>=1&&a[nwx][nwy]&&!used[nwx+dx[i]][nwy+dy[i]]);
      if(!f) return 0;
      return can(nwx,nwy,i);
}

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(v.first,v.second,i)){
                        used[nwx][nwy]=1;
                        q.push({nwx,nwy});
                  }
            }
      }
}

void solve(){
      cin>>m>>n>>k>>LL;
      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;
                  }
                  R[i][j]=j+mx1-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;
                  }
                  L[i][j]=j-mx2+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;
                  }
                  U[i][j]=i+mx1-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;
                  }
                  D[i][j]=i-mx2+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...