제출 #1334216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1334216		LIA	Walk (CEOI06_walk)	C++17	0 / 100	125 ms	22700 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
#define tpl tuple<ll, ll, ll, ll, ll, ll>

struct Seg {
  Seg *left = nullptr, *right = nullptr;
  int l, r, mid;
  int id = -1, lazy = -1;

  Seg(int l, int r) : l(l), r(r), mid((l + r) / 2) {}

  void ensure() {
    if (l == r)
      return;
    if (left == nullptr) {
      left = new Seg(l, mid);
      right = new Seg(mid + 1, r);
    }
  }

  void push() {
    if (lazy == -1)
      return;
    id = lazy;
    ensure();
    if (l != r) {
      left->lazy = lazy;
      right->lazy = lazy;
    }
    lazy = -1;
  }

  int q(int pos) {
    push();
    if (l == r)
      return id;
    ensure();
    if (pos <= mid)
      return left->q(pos);
    return right->q(pos);
  }

  void update(int a, int b, int V) {
    push();
    if (l > b || r < a)
      return;
    if (l >= a && r <= b) {
      lazy = V;
      push();
      return;
    }
    ensure();
    left->update(a, b, V);
    right->update(a, b, V);
  }
};

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

  ll dest_x, dest_y;
  cin >> dest_x >> dest_y;
  ll n;
  cin >> n;
  vector<tpl> vec;
  v<ll> y_val;

  y_val.push_back(dest_y);
  y_val.push_back(0);

  v<ll> B_bottom(n + 2), B_top(n + 2);

  lp(i, 0, n) {
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll lx = min(a, c), rx = max(a, c);
    ll ly = min(b, d), ry = max(b, d);

    if (lx >= dest_x)
      continue;

    rx = min(rx, dest_x);

    B_bottom[i + 1] = ly;
    B_top[i + 1] = ry;

    y_val.push_back(ly);
    y_val.push_back(ry);
    y_val.push_back(ly - 1);
    y_val.push_back(ry + 1);

    vec.push_back({lx, ly, rx, ry, 0, i + 1});
    vec.push_back({rx, ry, lx, ly, 1, i + 1});
  }

  sort(y_val.begin(), y_val.end());
  y_val.erase(unique(y_val.begin(), y_val.end()), y_val.end());

  auto get_y = [&](ll y) {
    return lower_bound(y_val.begin(), y_val.end(), y) - y_val.begin();
  };

  vec.push_back({0, 0, 0, 0, 1, 0});
  sort(vec.begin(), vec.end());

  Seg seg(0, y_val.size() - 1);
  seg.update(0, y_val.size() - 1, n + 1);

  v<v<ll>> dp(n + 2, v<ll>(2, 0));

  auto get_dist = [&](ll y, int hit) {
    if (hit == n + 1)
      return abs(y - dest_y);
    ll cost_bottom = abs(y - (B_bottom[hit] - 1)) + dp[hit][0];
    ll cost_top = abs(y - (B_top[hit] + 1)) + dp[hit][1];
    return min(cost_bottom, cost_top);
  };

  ll ans = 1e18;

  for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
    auto [cx, cy, ox, oy, type, idx] = *it;

    if (type == 1) {
      if (idx == 0) {
        int hit = seg.q(get_y(0));
        ans = dest_x + get_dist(0, hit);
      } else {
        ll y_bottom = oy;
        ll y_top = cy;

        int hit1 = seg.q(get_y(y_bottom - 1));
        dp[idx][0] = get_dist(y_bottom - 1, hit1);

        int hit2 = seg.q(get_y(y_top + 1));
        dp[idx][1] = get_dist(y_top + 1, hit2);
      }
    } else {
      ll y_bottom = cy;
      ll y_top = oy;
      seg.update(get_y(y_bottom), get_y(y_top), idx);
    }
  }

  cout << ans << "\n";
}

• Subtask 1: 0 / 100