Submission #1354522

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

pair<int, int> geth(int x, int y){
    int l = max(1, x - k + 1), r = x, lb = -1, rb = -1;
    while(l <= r){
        int md = (l + r) / 2;
        if(pfh[md][y] - pfh[x - k][y] > 0){
            lb = md;
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    if(lb == -1) return {-1, -1};
    l = lb, r = x;
    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){
    int l = max(1, y - g + 1), r = y, lb = -1, rb = -1;
    while(l <= r){
        int md = (l + r) / 2;
        if(pfv[x][md] - pfv[x][y - g] > 0){
            lb = md;
            r = md - 1;
        }else{
            l = md + 1;
        }
    }
    if(lb == -1) return {-1, -1};
    l = lb, r = y;
    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 == -1 || l2 == -1) return 0; 
    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 >> g >> 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<=g;j++){
            if(tb[i][j] == 'X') ++c;
        }
        if(c == 0) okv[i][1] = 1;
        for(int j = 2;j + g - 1<=m;j++){
            if(tb[i][j - 1] == 'X') --c;
            if(tb[i][j + g - 1] == 'X') ++c;
            if(c == 0) okv[i][j] = 1;
        }
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            pfh[i][j] = pfh[i - 1][j] + okh[i][j];
            pfv[i][j] = pfv[i][j - 1] + okv[i][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...