Submission #1364898

#TimeUsernameProblemLanguageResultExecution timeMemory
1364898enzyToy (CEOI24_toy)C++20
100 / 100
373 ms359248 KiB
#include<bits/stdc++.h>
using namespace std;
const int maxn=1510;
int v[maxn][maxn], aux[maxn][maxn], marc[maxn][maxn], n, m;
int spx[maxn][maxn], spy[maxn][maxn];
vector<int>pdx[maxn], pdy[maxn];

bool in(int x, int y){
    return 1<=x&&x<=n&&1<=y&&y<=m;
}

void dfs(int x, int y, int k, int l){
    // cerr << x << ' ' << y << '\n';
    marc[x][y]++;
    int lx, rx, ly, ry;
    int aux;

    lx=max(x-l+1,1); aux=x;
    while(lx<aux){
        int mid=(lx+aux)/2;
        if(spy[aux][y]-spy[mid-1][y]==0) aux=mid;
        else lx=mid+1;
    }

    ly=max(y-k+1,1); aux=y;
    while(ly<aux){
        int mid=(ly+aux)/2;
        if(spx[x][aux]-spx[x][mid-1]==0) aux=mid;
        else ly=mid+1;
    }

    rx=x+l-1; aux=x;
    while(aux<rx){
        int mid=(rx+aux+1)/2;
        if(spy[mid][y]-spy[aux-1][y]==0) aux=mid;
        else rx=mid-1;
    }
    ry=y+k-1; aux=y;
    while(aux<ry){
        int mid=(ry+aux+1)/2;
        if(spx[x][mid]-spx[x][aux-1]==0) aux=mid;
        else ry=mid-1;
    }

    // cerr << "ended bb\n";

    rx-=(l-1); ry-=(k-1); // fazendo ser o comeco do bloco

    // enta o comeco do bloco esta entre [lx,rx] e [ly,ry]

    if(in(x,y+1)&&marc[x][y+1]==0){
        // cerr << pdy[y+1].back() << '\n';
        int at=lower_bound(pdy[y+1].begin(),pdy[y+1].end(),lx)-pdy[y+1].begin();
        // cerr << at << ' ' << pdy[y+1].size() << ' ' << pdy[y+1][at] << '\n';
        if(pdy[y+1][at]<=rx) dfs(x,y+1,k,l);
        // cerr << "nope\n";
    }
    if(in(x,y-1)&&marc[x][y-1]==0){
        // cerr << pdy[y-1].back() << '\n';
        int at=lower_bound(pdy[y-1].begin(),pdy[y-1].end(),lx)-pdy[y-1].begin();
        if(pdy[y-1][at]<=rx) dfs(x,y-1,k,l);
    }
    if(in(x+1,y)&&marc[x+1][y]==0){
        // cerr << pdx[x+1].back() << '\n';
        int at=lower_bound(pdx[x+1].begin(),pdx[x+1].end(),ly)-pdx[x+1].begin();
        if(pdx[x+1][at]<=ry) dfs(x+1,y,k,l);
    }
    if(in(x-1,y)&&marc[x-1][y]==0){
        int at=lower_bound(pdx[x-1].begin(),pdx[x-1].end(),ly)-pdx[x-1].begin();
        if(pdx[x-1][at]<=ry) dfs(x-1,y,k,l);
    }
    // cerr << "!!! fim\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int k, l; cin >> m >> n >> k >> l;
    int xa, ya, xb, yb; cin >> ya >> xa >> yb >> xb; xa++; ya++; xb++; yb++;
    int xf, yf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char c; cin >> c;
            if(c=='X') v[i][j]=1;
            if(c=='*') xf=i, yf=j;
        }
    }


    auto pre=[&](){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) spx[i][j]=spx[i][j-1]+v[i][j]; // x cte

        for(int j=1;j<=m;j++)
            for(int i=1;i<=n;i++) spy[i][j]=spy[i-1][j]+v[i][j]; // y cte
    };
    // precomputar para checar se pd ou n ter um bloco comecando naquele lugar
    pre(); // primeiro fzr somas parciais
    // vendo pecas deitadas, com x cte
    for(int i=1;i<=n;i++){
        for(int j=1;j+k-1<=m;j++){
            if((spx[i][j+k-1]-spx[i][j-1])==0) pdx[i].push_back(j);
        }
        pdx[i].push_back(2*maxn);
    }
    for(int j=1;j<=m;j++){
        for(int i=1;i+l-1<=n;i++){
            if((spy[i+l-1][j]-spy[i-1][j])==0) pdy[j].push_back(i);
        }
        pdy[j].push_back(2*maxn);
    }

    int x, y;
    for(int i=ya;i<ya+k;i++) aux[xa][i]++;
    for(int i=xb;i<xb+l;i++) aux[i][yb]++;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) if(aux[i][j]==2) x=i, y=j;

    dfs(x,y,k,l);

    if(marc[xf][yf]) cout << "YES\n";
    else cout << "NO\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...