Submission #1354509

#TimeUsernameProblemLanguageResultExecution timeMemory
1354509nathlol2Toy (CEOI24_toy)C++20
73 / 100
1598 ms113212 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 1505;
int n, m, k, l, xh, yh, xv, yv, ex, ey, okh[N][N], okv[N][N], vis[N][N], dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
string tb[N];
queue<pair<int, int>> q;
set<int> h[N], v[N];

pair<int, int> geth(int x, int y){
    auto it = h[y].lower_bound(x - k + 1);
    if(it == h[y].end() || *it > x) return {-1, -1};
    int lb = *it, l = *it, r = x, rb;
    while(l <= r){
        int md = (l + r) / 2;
        if(okh[md][y]){
            rb = md;
            l = md + 1;
        }else{
            r = md - 1;
        }
    }
    return {lb, rb};
}

pair<int, int> getv(int x, int y){
    auto it = v[x].lower_bound(y - l + 1);
    if(it == v[x].end() || *it > y) return {-1, -1};
    int lb = *it, l = *it, r = y, rb;
    while(l <= r){
        int md = (l + r) / 2;
        if(okv[x][md]){
            rb = md;
            l = md + 1;
        }else{
            r = md - 1;
        }
    }
    return {lb, rb};
}

bool isect(int l1, int r1, int l2, int r2){
    if(l1 > l2) swap(l1, l2), swap(r1, r2);
    return r1 >= l2;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m >> n >> l >> k >> yv >> xv >> yh >> xh;
    ++xh, ++yh, ++xv, ++yv;
    for(int i = 1;i<=n;i++){
        cin >> tb[i];
        tb[i] = " " + tb[i];
        for(int j = 1;j<=m;j++){
            if(tb[i][j] == '*') ex = i, ey = j;
        }
    }
    for(int i = 1;i<=m;i++){
        int c = 0;
        for(int j = 1;j<=k;j++){
            if(tb[j][i] == 'X') ++c;
        }
        if(c == 0) okh[1][i] = 1;
        for(int j = 2;j + k - 1<=n;j++){
            if(tb[j - 1][i] == 'X') --c;
            if(tb[j + k - 1][i] == 'X') ++c;
            if(c == 0) okh[j][i] = 1;
        }
    }
    for(int i = 1;i<=n;i++){
        int c = 0;
        for(int j = 1;j<=l;j++){
            if(tb[i][j] == 'X') ++c;
        }
        if(c == 0) okv[i][1] = 1;
        for(int j = 2;j + l - 1<=m;j++){
            if(tb[i][j - 1] == 'X') --c;
            if(tb[i][j + l - 1] == 'X') ++c;
            if(c == 0) okv[i][j] = 1;
        }
    }
    for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) if(okh[i][j]) h[j].insert(i);
    for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) if(okv[i][j]) v[i].insert(j);
    q.push({xv, yh});
    vis[xv][yh] = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        auto [lh, rh] = geth(x, y);
        auto [lv, rv] = getv(x, y);
        for(int i = 0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            auto [lnh, rnh] = geth(nx, ny);
            auto [lnv, rnv] = getv(nx, ny);
            if(isect(lh, rh, lnh, rnh) && isect(lv, rv, lnv, rnv) && !vis[nx][ny]){
                vis[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
    cout << (vis[ex][ey] ? "YES" : "NO");
}
#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...