제출 #1342930

#제출 시각아이디문제언어결과실행 시간메모리
1342930po_rag526Toy (CEOI24_toy)C++20
0 / 100
17 ms4152 KiB
/**
 * author:  tuncypasha
 * file:    c.cpp
 * created: 14.03.2026 13:04
**/
#include <bits/stdc++.h>
#define pasha ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(v) begin(v), end(v)
using namespace std;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 15e2 + 5, B = 700, MAX = 1e6 + 5, oo = 1e+16;

char a[N][N];
bool ok1[N][N];
bool ok2[N][N];
int p[N][N];

int m,n;
int xh,yh,xv,yv;
bool used[1501][1501];
bool can[1501][1501];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

int ask(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];
}

bool ok(int r, int c){
  return (r >= 1 && r <= n && c >= 1 && c <= m && ok1[r][c] && ok2[r][c] && !used[r][c]);
}

void bfs(int x, int y) {
  queue<pair<int, int>> q;
  q.push({x, y});
  used[x][y] = true;
  while (!q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    for (int i = 0; i < 4; ++i) {
      int nx = p.ff + dx[i];
      int ny = p.ss + dy[i];
      if (ok(nx, ny)) {
        used[nx][ny] = true;
        q.push({nx, ny});
      }
    }
  }
}

void _() {
  int w, h, k, l, x1, y1, x2, y2; cin >> w >> h >> k >> l >> x1 >> y1 >> x2 >> y2;
  swap(w, h), swap(x1, y1), swap(x2, y2);
  xh = x1 + 1;
  yh = y1 + 1;
  xv = x2 + 1;
  yv = y2 + 1;
  ++x1, ++y1, ++x2, ++y2;
  n = w;
  m = h;
  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');
            }
      }
  // Elay


  // Tuncay

  auto intersect = [&](int X1, int Y1, int X2, int Y2) -> pair<int, int> {
    return {X2, Y1};
  };
  pair<int, int> beg = intersect(x1, y1, x2, y2);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] == 'X') continue;
      int lo = 1, hi = j - 1, best1 = j;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        int cnt = ask(i, mid, i, j);
        if (!cnt) {
          best1 = mid;
          hi = mid - 1;
        }
        else lo = mid + 1;
      }
      int best2 = j; lo = j + 1, hi = m;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        int cnt = ask(i, j, i, mid);
        if (!cnt) {
          best2 = mid;
          lo = mid + 1;
        }
        else hi = mid - 1;
      }
      ok1[i][j] = (best2 - best1 + 1 >= k);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] == 'X') continue;
      int lo = 1, hi = i - 1, best1 = i;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        int cnt = ask(mid, j, i, j);
        if (!cnt) {
          best1 = mid;
          hi = mid - 1;
        }
        else lo = mid + 1;
      }
      int best2 = i; lo = i + 1, hi = n;
      while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        int cnt = ask(i, j, mid, j);
        if (!cnt) {
          best2 = mid;
          lo = mid + 1;
        }
        else hi = mid - 1;
      }
      ok2[i][j] = (best2 - best1 + 1 >= l);
    }
  }
  int x = -1, y = -1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] == '*') {
        x = i;
        y = j;
        break;
      }
    }
  }
  bfs(beg.ff, beg.ss);
  cout << (used[x][y] ? "YES" : "NO") << '\n';
}

signed main() {
  pasha
  int t = 1;
  // cin >> t;
  for (int cs = 1; cs <= t; ++cs) {
    _();
    // cout << '\n';
  }
}
#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...