Submission #827942

#TimeUsernameProblemLanguageResultExecution timeMemory
827942null_aweMaze (JOI23_ho_t3)C++14
43 / 100
2096 ms433544 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> const int UNTIL = 4206900; vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1}; int LG2[UNTIL]; int csqrt[UNTIL], fsqrt[UNTIL]; void init() { LG2[1] = 0; for (int i = 2; i < UNTIL; ++i) LG2[i] = LG2[i >> 1] + 1; csqrt[1] = fsqrt[1] = 1; for (int i = 2; i < UNTIL; ++i) { fsqrt[i] = fsqrt[i - 1]; while ((fsqrt[i] + 1) * (fsqrt[i] + 1) <= i) ++fsqrt[i]; csqrt[i] = fsqrt[i]; if (fsqrt[i] * fsqrt[i] < i) ++csqrt[i]; } } struct VEB { int u, mn, mx, sz; VEB *summary; vector<VEB*> galaxy; inline int high(int k) { return k / sz; } inline int low(int k) { return k % sz; } inline int index(int k, int kk) { return k * sz + kk; } VEB(int u) : u(u) { mn = INT_MAX, mx = INT_MIN; if (u <= 2) summary = nullptr, galaxy.resize(0, nullptr); else { int ngalaxy = csqrt[u]; sz = (u + ngalaxy - 1) / ngalaxy; summary = new VEB(ngalaxy); galaxy.resize(ngalaxy, nullptr); for (int i = 0; i < ngalaxy - 1; ++i) galaxy[i] = new VEB(sz); galaxy[ngalaxy - 1] = new VEB(u - (ngalaxy - 1) * sz); } } void insert(int x) { if (mn == INT_MAX) mn = mx = x; else { if (x < mn) swap(x, mn); if (x > mx) mx = x; if (u <= 2) return; int i = high(x), j = low(x); if (galaxy[i]->mn == INT_MAX) summary->insert(i); galaxy[i]->insert(j); } } void erase(int x) { if (mn == INT_MAX) return; if (mn == mx) { mn = INT_MAX, mx = INT_MIN; return; } if (u <= 2) { if (x != mx) mn = mx; else if (x == mn) mn = INT_MAX, mx = INT_MIN; else if (x == 0) mn = 1; else mx = 0; return; } if (x == mn) { int i = summary->mn; if (i == INT_MAX) { mn = INT_MAX, mx = INT_MIN; return; } x = mn = index(i, galaxy[i]->mn); } int i = high(x), j = low(x); galaxy[i]->erase(j); if (galaxy[i]->mn == INT_MAX) summary->erase(i); if (x == mx) { if (summary->mx == INT_MIN) mx = mn; else { i = summary->mx; mx = index(i, galaxy[i]->mx); } } } int lower_bound(int x) { if (x <= mn) return mn; if (u <= 2) { if (x <= mx) return mx; return INT_MAX; } int i = high(x), j = low(x); if (j <= galaxy[i]->mx) j = galaxy[i]->lower_bound(j); else { i = summary->lower_bound(i + 1); j = galaxy[i]->mn; } return index(i, j); } }; VEB* build_veb(int u) { VEB* root = new VEB(u); for (int i = 0; i < u; ++i) root->insert(i); return root; } struct Sustree { int n, m; vector<VEB*> has; Sustree() {} Sustree(int n, int m) : n(n), m(m), has(4 * n, nullptr) {} void build(int t, int tl, int tr) { has[t] = build_veb(m + 1); if (tl == tr) return; build(2 * t, tl, (tl + tr) / 2); build(2 * t + 1, (tl + tr) / 2 + 1, tr); } void build() { build(1, 0, n - 1); } void upd(int t, int tl, int tr, int p, int py) { if (tl == tr) { has[t]->erase(py); return; } if (p <= (tl + tr) / 2) upd(2 * t, tl, (tl + tr) / 2, p, py); else upd(2 * t + 1, (tl + tr) / 2 + 1, tr, p, py); int a = has[2 * t]->lower_bound(py); int b = has[2 * t + 1]->lower_bound(py); if (a != py && b != py) { has[t]->erase(py); } } void upd(int x, int y) { upd(1, 0, n - 1, x, y); } pii qry(int t, int tl, int tr, int l, int r, int lo, int hi) { l = max(l, tl), r = min(r, tr); if (l > r) return {-1, -1}; if (tl == l && tr == r) { int gr = has[t]->lower_bound(lo); if (gr > hi) return {-1, -1}; if (tl == tr) { return {tl, gr}; } int mm = (tl + tr) / 2; if (has[2 * t]->lower_bound(lo) <= hi) return qry(2 * t, tl, mm, l, r, lo, hi); return qry(2 * t + 1, mm + 1, tr, l, r, lo, hi); } int mm = (tl + tr) / 2; pii f = qry(2 * t, tl, mm, l, r, lo, hi); if (f.first >= 0) return f; return qry(2 * t + 1, mm + 1, tr, l, r, lo, hi); } pii qry(int x1, int y1, int x2, int y2) { return qry(1, 0, n - 1, max(x1, 0), min(x2, n - 1), max(y1, 0), min(y2, m - 1)); } }; int main() { init(); ios_base::sync_with_stdio(false); cin.tie(NULL); 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]; if (r > c) { vector<string> arr2(c); for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { arr2[j] += arr[i][j]; } } swap(arr, arr2); swap(r, c); swap(sx, sy); swap(gx, gy); } // . = empty // # = wall Sustree sus(r, c); sus.build(); vector<vector<int>> dists(r, vector<int>(c, INT_MAX)); dists[sx][sy] = 0; sus.upd(sx, sy); 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]; sus.upd(nx, ny); } } while (q.size()) { vector<pii> nq; for (pii p : q) { int x = p.first, y = p.second; if (x > 0 && dists[x - 1][y] <= dists[x][y]) { // query down: int cur; while ((cur = sus.qry(x + n, y - n + 1, x + n, y + n - 1).second) != -1) { nq.push_back({x + n, cur}); dists[x + n][cur] = dists[x][y] + 1; sus.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; sus.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; sus.upd(x + n - 1, y + n); } } else if (y < r - 1 && dists[x][y + 1] <= dists[x][y]) { // query left: int cur; while ((cur = sus.qry(x - n + 1, y - n, x + n - 1, y - n).first) != -1) { nq.push_back({cur, y - n}); dists[cur][y - n] = dists[x][y] + 1; sus.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; sus.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; sus.upd(x + n, y - n + 1); } } else { // query all: for (int i = -n; i <= n; i += 2 * n) { int cx = x + i, cyl = y - n + 1, cyr = y + n - 1, cur; while ((cur = sus.qry(cx, cyl, cx, cyr).second) != -1) { nq.push_back({cx, cur}); dists[cx][cur] = dists[x][y] + 1; sus.upd(cx, cur); } } pii cur; while ((cur = sus.qry(x - n + 1, y - n, x + n - 1, y + n)).first != -1) { int nx = cur.first, ny = cur.second; nq.push_back({nx, ny}); dists[nx][ny] = dists[x][y] + 1; sus.upd(nx, ny); } } } 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]; sus.upd(nx, ny); } } q = nq; } cout << dists[gx][gy] << '\n'; return 0; }

Compilation message (stderr)

Main.cpp:12:5: warning: built-in function 'csqrt' declared as non-function [-Wbuiltin-declaration-mismatch]
   12 | int csqrt[UNTIL], fsqrt[UNTIL];
      |     ^~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...