제출 #1342851

#제출 시각아이디문제언어결과실행 시간메모리
1342851po_rag526Toy (CEOI24_toy)C++20
100 / 100
961 ms195580 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#define ll int
#define double double long
#define fori(i,j,k) for(ll i=j; i<=k;i++)
#define study ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define all(s) s.begin(),s.end()
#define ins insert
#define ss second
#define ff first
#ifndef DB
#define DB 0
#endif
#define debugl(l) if constexpr((l)<DB)
#define debug debugl(0)
const ll sz=1500+10;
ll INF=1e9;
ll mod=1e9+7;
ll add=1e2;
ll w,h,k,l;
vector<vector<ll>>grid(sz,vector<ll>(sz,2)),dist(sz,vector<ll>(sz,INF));
ll tx,ty;
vector<set<ll>>cols,rows;
ll dx[]={0,1,0,-1};
ll dy[]={-1,0,1,0};
void work(){
    cin>>w>>h>>k>>l;
    ll x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    cols.resize(w+10);
    rows.resize(h+10);
    fori(i,0,h-1){
        string s;
        cin>>s;
        rows[i].ins(-1);
        rows[i].ins(w);
        fori(j,0,w-1){
            cols[j].ins(-1);
            cols[j].ins(h);
            if(s[j]=='.'){
                grid[i][j]=0;
            }
            if(s[j]=='X'){
                grid[i][j]=2;
                cols[j].ins(i);
                rows[i].ins(j);
            }
            if(s[j]=='*'){
                tx=i;
                ty=j;
                grid[i][j]=1;
            }
        }
    }
    queue<pair<ll,ll>>q;
    ll c=x2,r=y1;
    q.push({r,c});
    dist[r][c]=0;
    while(!q.empty()){
        ll cs=q.front().ss,rs=q.front().ff;
        q.pop();
        auto it=rows[rs].lower_bound(cs);
        ll obx2=*it;
        it--;
        ll obx1=*it;
        it=cols[cs].lower_bound(rs);
        ll oyx2=*it;
        it--;
        ll oyx1=*it;
        fori(m,0,3){
            ll cc=cs+dx[m];
            ll rc=rs+dy[m];
            if(cc<0 || rc<0 || cc>=w || rc>=h)
            continue;
            if(grid[rc][cc]==2)
            continue;
            it=rows[rc].lower_bound(cc);
            ll obx4=*it;
            it--;
            ll obx3=*it;
            it=cols[cc].lower_bound(rc);
            ll oyx4=*it;
            it--;
            ll oyx3=*it;
            oyx4=min(oyx4,oyx2);
            oyx3=max(oyx3,oyx1);
            obx4=min(obx4,obx2);
            obx3=max(obx3,obx1);
            //cout<<rc<<" "<<cc<<" "<<oyx4<<" "<<oyx3<<" "<<obx4<<" "<<obx3<<endl;
            if((obx4-obx3-1)>=k and (oyx4-oyx3-1)>=l and dist[rc][cc]>(dist[rs][cs]+1)){
                dist[rc][cc]=dist[rs][cs]+1;
                q.push({rc,cc});
            }
        }

    }
    if(dist[tx][ty]==INF)
    cout<<"NO";
    else
    cout<<"YES";
}
int main()
{
    //#ifndef LOCAL
    // freopen("log1.txt","r",stdin);
    // freopen("log2.txt","w",stdout);
    //#endif
    study;
    ll t=1;
    //cin>>t;
    fori(i,1,t){
        work();
    }
}
#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...