Submission #283874

#	Time	Username	Problem	Language	Result	Execution time	Memory
283874		rama_pang	Golf (JOI17_golf)	C++14	100 / 100	6773 ms	426312 KiB

golf

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

class SegmentTree {
 public:
  int sz;
  vector<set<pair<int, int>>> tree;

  SegmentTree() {}
  SegmentTree(int sz) : sz(sz), tree(2 * sz) {}

  void Add(int l, int r, int v, int id = -1) {
    for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) tree[l++].emplace(v, id);
      if (r & 1) tree[--r].emplace(v, id);
    }
  }

  int FindMax(int p, int x) { // Find maximum <= x
    int res = 0;
    for (p += sz; p > 0; p /= 2) {
      if (!tree[p].empty()) {
        auto it = tree[p].upper_bound({x, sz + 1});
        if (it != begin(tree[p])) {
          res = max(res, prev(it)->first);
        }
      }
    }
    return res;
  }

  int FindMin(int p, int x) { // Find minimum >= x
    int res = sz - 1;
    for (p += sz; p > 0; p /= 2) {
      if (!tree[p].empty()) {
        auto it = tree[p].lower_bound({x, -1});
        if (it != end(tree[p])) {
          res = min(res, it->first);
        }        
      }
    }
    return res;
  }

  vector<int> FindIntersection(int p, int x, int y) {
    vector<int> res;
    for (p += sz; p > 0; p /= 2) {
      if (tree[p].empty()) {
        continue;
      }
      auto &s = tree[p];
      auto it = s.lower_bound({x, -1});
      while (it != end(s) && it->first <= y) {
        res.emplace_back(it->second);
        it = s.erase(it);
      }
    }
    sort(begin(res), end(res));
    res.resize(unique(begin(res), end(res)) - begin(res));
    return res;
  }
};

void Read(int &S, int &T, int &U, int &V, int &N, 
          vector<int> &A, vector<int> &B, vector<int> &C, vector<int> &D) {

  cin >> S >> T >> U >> V >> N;
  A.resize(N), B.resize(N), C.resize(N), D.resize(N);

  vector<int> xcoord = {S, U};
  vector<int> ycoord = {T, V};
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    xcoord.emplace_back(A[i]);
    xcoord.emplace_back(B[i]);
    ycoord.emplace_back(C[i]);
    ycoord.emplace_back(D[i]);
  }

  sort(begin(xcoord), end(xcoord));
  sort(begin(ycoord), end(ycoord));
  xcoord.resize(unique(begin(xcoord), end(xcoord)) - begin(xcoord));
  ycoord.resize(unique(begin(ycoord), end(ycoord)) - begin(ycoord));

  const auto GetPosition = [&](const vector<int> &a, int x) {
    return lower_bound(begin(a), end(a), x) - begin(a);
  };

  S = GetPosition(xcoord, S);
  T = GetPosition(ycoord, T);
  U = GetPosition(xcoord, U);
  V = GetPosition(ycoord, V);

  for (int i = 0; i < N; i++) {
    A[i] = GetPosition(xcoord, A[i]);
    B[i] = GetPosition(xcoord, B[i]);
    C[i] = GetPosition(ycoord, C[i]);
    D[i] = GetPosition(ycoord, D[i]);
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int S, T, U, V, N;
  vector<int> A, B, C, D;
  Read(S, T, U, V, N, A, B, C, D);

  vector<SegmentTree> boundary(2, SegmentTree(2 * N + 2));
  for (int i = 0; i < N; i++) {
    boundary[0].Add(C[i] + 1, D[i] - 1, A[i]);
    boundary[0].Add(C[i] + 1, D[i] - 1, B[i]);
    boundary[1].Add(A[i] + 1, B[i] - 1, C[i]);
    boundary[1].Add(A[i] + 1, B[i] - 1, D[i]);
  }

  vector<array<int, 4>> lines;
  for (int i = 0; i < N; i++) {
    lines.push_back({A[i], C[i], D[i], 0});
    lines.push_back({B[i], C[i], D[i], 0});
    lines.push_back({C[i], A[i], B[i], 1});
    lines.push_back({D[i], A[i], B[i], 1});
  }

  lines.push_back({S, T, T, 0});
  lines.push_back({T, S, S, 1});
  lines.push_back({U, V, V, 0});
  lines.push_back({V, U, U, 1});

  for (auto &l : lines) {
    l[1] = boundary[l[3] ^ 1].FindMax(l[0], l[1] - 1);
    l[2] = boundary[l[3] ^ 1].FindMin(l[0], l[2] + 1);
  }

  vector<SegmentTree> intersect(2, SegmentTree(2 * N + 2));
  for (int i = 0; i < (int) lines.size(); i++) {
    intersect[lines[i][3]].Add(lines[i][1], lines[i][2], lines[i][0], i);
  }

  queue<int> q;
  vector<int> dist(4 * N + 4, -1);
  for (int i = 0; i < (int) lines.size(); i++) {
    if (lines[i][3] == 0) { // vertical
      if (lines[i][0] == S && lines[i][1] <= T && T <= lines[i][2]) {
        q.emplace(i);
        dist[i] = 1;
      }
    } else { // horizontal
      if (lines[i][0] == T && lines[i][1] <= S && S <= lines[i][2]) {
        q.emplace(i);
        dist[i] = 1;
      }
    }
  }

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    auto l = lines[u];
    auto adj = intersect[l[3] ^ 1].FindIntersection(l[0], l[1], l[2]);
    for (auto v : adj) {
      if (dist[v] == -1) {
        dist[v] = dist[u] + 1;
        q.emplace(v);
      }
    }
  }

  int ans = 1e9;
  for (int i = 0; i < (int) lines.size(); i++) {
    if (lines[i][3] == 0) { // vertical
      if (lines[i][0] == U && lines[i][1] <= V && V <= lines[i][2]) {
        ans = min(ans, dist[i]);
      }
    } else { // horizontal
      if (lines[i][0] == V && lines[i][1] <= U && U <= lines[i][2]) {
        ans = min(ans, dist[i]);
      }
    }
  }

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

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