Submission #825499

#	Time	Username	Problem	Language	Result	Execution time	Memory
825499		null_awe	Maze (JOI23_ho_t3)	C++14	51 / 100	2083 ms	135344 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

struct Segtree {

  int n;
  vector<bool> on;

  Segtree() {}

  Segtree(int n) : n(n), on(4 * n, 1) {}

  void upd(int t, int tl, int tr, int p) {
    if (tl == tr) on[t] = false;
    else {
      int m = (tl + tr) / 2;
      if (p <= m) upd(2 * t, tl, m, p);
      else upd(2 * t + 1, m + 1, tr, p);
      on[t] = on[2 * t] | on[2 * t + 1];
    }
  }

  int qry(int t, int tl, int tr, int l, int r) {
    l = max(l, tl), r = min(r, tr);
    if (l > r) return -1;
    if (tl == l && tr == r && !on[t]) return -1;
    if (tl == tr) {
      assert(on[t]);
      return tl;
    }
    int m = (tl + tr) / 2;
    int f = qry(2 * t, tl, m, l, r);
    if (f >= 0) return f;
    return qry(2 * t + 1, m + 1, tr, l, r);
  }
};

struct Groups {

  int r, c;
  vector<Segtree> rs, cs;

  Groups() {}

  Groups(int r, int c) : r(r), c(c) {
    for (int i = 0; i < r; ++i) {
      Segtree tmp(c);
      rs.push_back(tmp);
    }
    for (int i = 0; i < c; ++i) {
      Segtree tmp(r);
      cs.push_back(tmp);
    }
  }

  void upd(int x, int y) {
    // cout << x << ' ' << y << endl;
    rs[x].upd(1, 0, c - 1, y);
    cs[y].upd(1, 0, r - 1, x);
    // cout << "done" << endl;
  }

  int qrow(int row, int l, int rr) {
    if (row < 0 || row >= r) return -1;
    return rs[row].qry(1, 0, c - 1, max(l, 0), min(rr, c - 1));
  }

  int qcol(int col, int l, int rr) {
    if (col < 0 || col >= c) return -1;
    return cs[col].qry(1, 0, r - 1, max(l, 0), min(rr, r - 1));
  }
};

int main() {
  int r, c, n; cin >> r >> c >> n;
  int sx, sy; cin >> sx >> sy; --sx, --sy;
  int gx, gy; cin >> gx >> gy; --gx, --gy;
  vector<string> arr(r);
  for (int i = 0; i < r; ++i) cin >> arr[i];
  // . = empty
  // # = wall
  Groups groups(r, c);
  vector<vector<int>> dists(r, vector<int>(c, INT_MAX));
  dists[sx][sy] = 0;
  // cout << dists[gx][gy] << '\n';
  groups.upd(sx, sy);
  // cout << groups.qrow(sx, sy, sy) << endl;
  vector<pii> q; q.push_back({sx, sy});
  queue<pii> rq; for (pii _p : q) rq.push(_p);
  while (rq.size()) {
    pii front = rq.front(); rq.pop();
    int xx = front.first, yy = front.second;
    for (int d = 0; d < 4; ++d) {
      int nx = xx + dx[d], ny = yy + dy[d];
      if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
      if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
      rq.push({nx, ny});
      q.push_back({nx, ny});
      dists[nx][ny] = dists[xx][yy];
      groups.upd(nx, ny);
    }
  }
  while (q.size()) {
    // for (int i = 0; i < r; ++i) {
      // for (int j = 0; j < c; ++j) cout << dists[i][j] << ' ';
      // cout << endl;
    // }
    // break;
    // cout << "here" << endl;
    // break;
    vector<pii> nq;
    for (pii p : q) {
      int x = p.first, y = p.second;
      // cout << x << ' ' << y << '\n';
      // if (x > 0 && dists[x - 1][y] <= dists[x][y]) {
      //     // cout << "t1" << endl;
      //   // query up:
      //   int cur;
      //   while ((cur = groups.qrow(x + n, y - n + 1, y + n - 1)) != -1) {
      //     nq.push_back({x + n, cur});
      //     dists[x + n][cur] = dists[x][y] + 1;
      //     groups.upd(x + n, cur);
      //   }
      //   if (x + n - 1 < r && y - n >= 0 && dists[x + n - 1][y - n] == INT_MAX) {
      //     nq.push_back({x + n - 1, y - n});
      //     dists[x + n - 1][y - n] = dists[x][y] + 1;
      //     groups.upd(x + n - 1, y - n);
      //   }
      //   if (x + n - 1 < r && y + n < c && dists[x + n - 1][y - n] == INT_MAX) {
      //     nq.push_back({x + n - 1, y + n});
      //     dists[x + n - 1][y + n] = dists[x][y] + 1;
      //     groups.upd(x + n - 1, y + n);
      //   }
      // } else if (x < r - 1 && dists[x + 1][y] <= dists[x][y]) {
      //     // cout << "t2" << endl;
      //   // query down:
      //   int cur;
      //   while ((cur = groups.qrow(x - n, y - n + 1, y + n - 1)) != -1) {
      //     nq.push_back({x - n, cur});
      //     dists[x - n][cur] = dists[x][y] + 1;
      //     groups.upd(x - n, cur);
      //   }
      //   if (x - n + 1 >= 0 && y - n >= 0 && dists[x - n + 1][y - n] == INT_MAX) {
      //     nq.push_back({x - n + 1, y - n});
      //     dists[x - n + 1][y - n] = dists[x][y] + 1;
      //     groups.upd(x - n + 1, y - n);
      //   }
      //   if (x - n + 1 >= 0 && y + n < c && dists[x - n + 1][y - n] == INT_MAX) {
      //     nq.push_back({x - n + 1, y + n});
      //     dists[x - n + 1][y + n] = dists[x][y] + 1;
      //     groups.upd(x - n + 1, y + n);
      //   }
      // } else if (y > 0 && dists[x][y - 1] <= dists[x][y]) {
      //     // cout << "t3" << endl;
      //   // query left:
      //   int cur;
      //   while ((cur = groups.qcol(y + n, x - n + 1, x + n - 1)) != -1) {
      //     nq.push_back({cur, y + n});
      //     dists[cur][y + n] = dists[x][y] + 1;
      //     groups.upd(cur, y + n);
      //   }
      //   if (y + n - 1 < c && x - n >= 0 && dists[x - n][y + n - 1] == INT_MAX) {
      //     nq.push_back({x - n, y + n - 1});
      //     dists[x - n][y + n - 1] = dists[x][y] + 1;
      //     groups.upd(x - n, y + n - 1);
      //   }
      //   if (y + n - 1 < c && x + n < r && dists[x + n][y + n - 1] == INT_MAX) {
      //     nq.push_back({x + n, y + n - 1});
      //     dists[x + n][y + n - 1] = dists[x][y] + 1;
      //     groups.upd(x + n, y + n - 1);
      //   }
      // } else if (y < r - 1 && dists[x][y + 1] <= dists[x][y]) {
      //     // cout << "t4" << endl;
      //   // query right:
      //   int cur;
      //   while ((cur = groups.qcol(y - n, x - n + 1, x + n - 1)) != -1) {
      //     nq.push_back({cur, y - n});
      //     dists[cur][y - n] = dists[x][y] + 1;
      //     groups.upd(cur, y - n);
      //   }
      //   if (y - n + 1 >= 0 && x - n >= 0 && dists[x - n][y - n + 1] == INT_MAX) {
      //     nq.push_back({x - n, y - n + 1});
      //     dists[x - n][y - n + 1] = dists[x][y] + 1;
      //     groups.upd(x - n, y - n + 1);
      //   }
      //   if (y - n + 1 >= 0 && x + n < r && dists[x + n][y - n + 1] == INT_MAX) {
      //     nq.push_back({x + n, y - n + 1});
      //     dists[x + n][y - n + 1] = dists[x][y] + 1;
      //     groups.upd(x + n, y - n + 1);
      //   }
      // } else {
        // query all:
        for (int i = -n; i <= n; ++i) {
          int cx = x + i, cyl = y - n, cyr = y + n;
          if (abs(i) == n) ++cyl, --cyr;
          int cur;
          while ((cur = groups.qrow(cx, cyl, cyr)) != -1) {
            nq.push_back({cx, cur});
            dists[cx][cur] = dists[x][y] + 1;
            groups.upd(cx, cur);
          }
        }
      // }
    }
    queue<pii> rq; for (pii _p : nq) rq.push(_p);
    while (rq.size()) {
      pii front = rq.front(); rq.pop();
      int xx = front.first, yy = front.second;
      for (int d = 0; d < 4; ++d) {
        int nx = xx + dx[d], ny = yy + dy[d];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
        rq.push({nx, ny});
        nq.push_back({nx, ny});
        dists[nx][ny] = dists[xx][yy];
        groups.upd(nx, ny);
      }
    }
    q = nq;
  }
  cout << dists[gx][gy] << '\n';
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 0 / 16
• Subtask 4: 19 / 19
• Subtask 5: 5 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6