Submission #106936

#	Time	Username	Problem	Language	Result	Execution time	Memory
106936		FlappyFish	Golf (JOI17_golf)	C++14	100 / 100	5937 ms	494680 KiB

golf

#include <bits/stdc++.h>
using namespace std;
const int U_MAX = 45678999;
const int MAX = 262144;
int sum[U_MAX], left_son[U_MAX], right_son[U_MAX];
struct event {
  int x, y, type;
  event(int a, int b, int t): x(a), y(b), type(t) {
  }
  bool operator <(const event &a) const {
    if (x != a.x) {
      return x < a.x;
    } else if (type != a.type) {
      return type < a.type;
    } else {
      return y < a.y;
    }
  }
};
struct range {
  int x, L, R;
  range(int a, int l, int r): x(a), L(l), R(r) {
  }
};
int main() {
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int n, sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  cin >> n;
  vector<int> vec_x, vec_y;
  auto add_point = [&] (int x, int y) {
    vec_x.push_back(x);
    vec_y.push_back(y);
  };
  add_point(sx, sy);
  add_point(tx, ty);
  vector<int> xl(n), yl(n), xr(n), yr(n);
  for (int i = 0; i < n; i++) {
    cin >> xl[i] >> xr[i] >> yl[i] >> yr[i];
    add_point(xl[i], yl[i]);
    add_point(xr[i], yr[i]);
  }
  auto normalize = [&] (vector<int> &vec) {
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
  };
  normalize(vec_x);
  normalize(vec_y);
  auto get_idx_x = [&] (int &x) {
    x = lower_bound(vec_x.begin(), vec_x.end(), x) - vec_x.begin() + 1;
  };
  auto get_idx_y = [&] (int &y) {
    y = lower_bound(vec_y.begin(), vec_y.end(), y) - vec_y.begin() + 1;
  };
  get_idx_x(sx);
  get_idx_y(sy);
  get_idx_x(tx);
  get_idx_y(ty);
  for (int i = 0; i < n; i++) {
    get_idx_x(xl[i]);
    get_idx_y(yl[i]);
    get_idx_x(xr[i]);
    get_idx_y(yr[i]);
  }
  int node_cnt = 0;
  function<int (int &, int, int, int, int)> add_in = [&] (int &u, int l, int r, int qx, int qy) {
    if (!u) {
      node_cnt++;
      u = node_cnt;
    }
    if (l == r) {
      if (sum[u]) {
        return 0;
      } else {
        sum[u] = qy + 1;
        return 1;
      }
    } else {
      int mid = (l + r) / 2, result = 0;
      if (qx <= mid) {
        result = add_in(left_son[u], l, mid, qx, qy);
      } else {
        result = add_in(right_son[u], mid + 1, r, qx, qy);
      }
      sum[u] += result;
      return result;
    }
  };
  function<void (vector<int> &, int, int, int, int, int, int, int)> add_out = [&] (vector<int> &root, int u, int l, int r, int ql, int qr, int qx, int qy) {
    if (l == ql && r == qr) {
      add_in(root[u], 0, MAX - 1, qx, qy);
    } else {
      int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
      if (qr <= mid) {
        add_out(root, x, l, mid, ql, qr, qx, qy);
      } else if (ql > mid) {
        add_out(root, y, mid + 1, r, ql, qr, qx, qy);
      } else {
        add_out(root, x, l, mid, ql, mid, qx, qy);
        add_out(root, y, mid + 1, r, mid + 1, qr, qx, qy);
      }
    }
  };
  auto init = [&] (vector<int> &root) {
    vector<event> eve;
    eve.emplace_back(sx, sy, 0);
    eve.emplace_back(tx, ty, 0);
    for (int i = 0; i < n; i++) {
      eve.emplace_back(xl[i], yl[i], 1);
      eve.emplace_back(xl[i], yr[i], 1);
      eve.emplace_back(xr[i], yl[i], -1);
      eve.emplace_back(xr[i], yr[i], -1);
      eve.emplace_back(xl[i], yl[i], 0);
      eve.emplace_back(xr[i], yl[i], 0);
    }
    sort(eve.begin(), eve.end());
    set<int> important;
    important.insert(0);
    important.insert(MAX - 1);
    vector<range> result;
    for (auto e : eve) {
      int x = e.x, y = e.y, type = e.type;
      if (type == 1) {
        important.insert(y);
      } else if (type == -1) {
        important.erase(y);
      } else {
        auto it = important.upper_bound(y);
        int R = *it, L = *--it;
        add_out(root, 0, 0, MAX - 1, L, R, x, result.size());
        result.emplace_back(x, L, R);
      }
    }
    return result;
  };
  auto reverse_xy = [&] () {
    swap(sx, sy);
    swap(tx, ty);
    swap(xl, yl);
    swap(xr, yr);
  };
  vector<int> root_x(MAX * 2), root_y(MAX * 2);
  auto range_x = init(root_x);
  reverse_xy();
  auto range_y = init(root_y);
  reverse_xy();
  vector<int> dis_x(range_x.size(), INT_MAX), dis_y(range_y.size(), INT_MAX);
  queue<pair<int, int> > que;
  for (int i = 0; i < range_x.size(); i++) {
    if (range_x[i].x == sx && sy >= range_x[i].L && sy <= range_x[i].R) {
      dis_x[i] = 1;
      que.emplace(i, 0);
    }
  }
  for (int i = 0; i < range_y.size(); i++) {
    if (range_y[i].x == sy && sx >= range_y[i].L && sx <= range_y[i].R) {
      dis_y[i] = 1;
      que.emplace(i, 1);
    }
  }
  function<int (int, int, int, int, int, int, int)> fast_in = [&] (int u, int l, int r, int ql, int qr, int qv, int xy) {
    if (!u || !sum[u]) {
      return 0;
    } else if (l == r) {
      int v = sum[u] - 1;
      auto &dis = xy ? dis_x : dis_y;
      if (dis[v] == INT_MAX) {
        dis[v] = qv;
        que.emplace(v, !xy);
      }
      sum[u] = 0;
      return 1;
    } else {
      int mid = (l + r) / 2, result = 0;
      if (qr <= mid) {
        result += fast_in(left_son[u], l, mid, ql, qr, qv, xy);
      } else if (mid < ql) {
        result += fast_in(right_son[u], mid + 1, r, ql, qr, qv, xy);
      } else {
        result += fast_in(left_son[u], l, mid, ql, mid, qv, xy);
        result += fast_in(right_son[u], mid + 1, r, mid + 1, qr, qv, xy);
      }
      sum[u] -= result;
      return result;
    }
  };
  function<void (vector<int> &, int, int, int, int, int, int, int, int)> fast_out = [&] (vector<int> &root, int u, int l, int r, int pos, int ql, int qr, int qv, int xy) {
    fast_in(root[u], 0, MAX - 1, ql, qr, qv, xy);
    if (l == r) {
      return;
    } else {
      int mid = (l + r) / 2, x = u + 1, y = u + (mid - l + 1) * 2;
      if (pos <= mid) {
        fast_out(root, x, l, mid, pos, ql, qr, qv, xy);
      } else {
        fast_out(root, y, mid + 1, r, pos, ql, qr, qv, xy);
      }
    }
  };
  while (!que.empty()) {
    int u = que.front().first, xy = que.front().second;
    que.pop();
    if (xy == 0) {
      if (range_x[u].x == tx && ty >= range_x[u].L && ty <= range_x[u].R) {
        cout << dis_x[u] << endl;
        return 0;
      } else {
        fast_out(root_y, 0, 0, MAX - 1, range_x[u].x, range_x[u].L, range_x[u].R, dis_x[u] + 1, 0);
      }
    } else {
      if (range_y[u].x == ty && tx >= range_y[u].L && tx <= range_y[u].R) {
        cout << dis_y[u] << endl;
        return 0;
      } else {
        fast_out(root_x, 0, 0, MAX - 1, range_y[u].x, range_y[u].L, range_y[u].R, dis_y[u] + 1, 1);
      }
    }
  }
  return 0;
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:153:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < range_x.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~
golf.cpp:159:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < range_y.size(); i++) {
                   ~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70