Submission #276059

---

Source Code Expand

#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
using namespace std;

#define DEBUG(x) cerr << #x << " = " << x << endl

const int INF = (int)1e9;

struct P {
  int x, y;
  P() { }
  P(int x_, int y_) : x(x_), y(y_) { }
};

P transform45(int x, int y) {
  return P(x - y, x + y);
}

struct LCA {
  int N, logN;
  vector<vector<int>> G;
  vector<int> depth;
  vector<vector<int>> parent;

  LCA(int size) : N(size), G(size), depth(size) {
    logN = 0;
    for(int x = 1; x < N; x *= 2) logN++;
    parent.assign(max(logN, 1), vector<int>(N));
  }

  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }

  void dfs(int v, int par, int dep) {
    depth[v] = dep;
    parent[0][v] = par;
    for(int next : G[v]) {
      if(next != par) dfs(next, v, dep + 1);
    }
  }

  void init(int root) {
    dfs(root, -1, 0);
    for(int k = 1; k < logN; k++) {
      for(int v = 0; v < N; v++) {
        if(parent[k - 1][v] == -1) parent[k][v] = -1;
        else parent[k][v] = parent[k - 1][parent[k - 1][v]];
      }
    }
  }

  int lca(int u, int v) {
    if(depth[u] > depth[v]) swap(u, v);
    for(int k = 0; k < logN; k++) {
      if(((depth[v] - depth[u]) >> k) & 1) {
        v = parent[k][v];
      }
    }
    if(u == v) return u;
    for(int k = logN - 1; k >= 0; k--) {
      if(parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

enum class EventType {
  Add,
  Remove,
  Point
};

struct Event {
  int y;
  int index;
  EventType type;
  Event() { }
  Event(int y_, int index_, EventType type_) : y(y_), index(index_), type(type_) { }
  bool operator <(const Event &rhs) const {
    return y < rhs.y;
  }
};

struct BIT {
  int N;
  vector<set<pair<int, int>>> data;
  BIT(int n) : N(n), data(n + 1) { }
  void add(int a, int b, int index) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x].insert(make_pair(b, index));
    }
  }
  void remove(int a, int b, int index) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x].erase(make_pair(b, index));
    }
  }
  pair<int, int> successor(int l, int r) {
    pair<int, int> ret = make_pair(INF, -1);
    for(int x = l; x > 0; x -= x & -x) {
      set<pair<int, int>>::iterator ub = data[x].upper_bound(make_pair(r, -1));
      if(ub != data[x].end()) {
        ret = min(ret, *ub);
      }
    }
    return ret;
  }
  void print() {
    set<pair<int, int>> S;
    for(int x = N; x > 0; x -= x & -x) {
      S.insert(data[x].begin(), data[x].end());
    }
    for(pair<int, int> s : S) {
      cerr << "l = " << s.first << ", index = " << s.second << endl;
    }
  }
};

int main() {
  int N; cin >> N;
  vector<vector<P>> square(N + 1, vector<P>(4));
  vector<int> Xs, Ys;
  for(int i = 0; i < N; ++i) {
    int x, y, r;
    cin >> x >> y >> r;
    square[i][0] = transform45(x + r, y);
    square[i][1] = transform45(x, y + r);
    square[i][2] = transform45(x - r, y);
    square[i][3] = transform45(x, y - r);
    for(int k = 0; k < 4; ++k) {
      Xs.push_back(square[i][k].x);
      Ys.push_back(square[i][k].y);
    }
  }

  square[N][0] = transform45(0 + INF, 0);
  square[N][1] = transform45(0, 0 + INF);
  square[N][2] = transform45(0 - INF, 0);
  square[N][3] = transform45(0, 0 - INF);
  for(int k = 0; k < 4; ++k) {
    Xs.push_back(square[N][k].x);
    Ys.push_back(square[N][k].y);
  }

  int M; cin >> M;
  vector<pair<P, P>> query(M);
  for(int i = 0; i < M; ++i) {
    int x, y;
    P tr;

    cin >> x >> y;
    tr = transform45(x, y);
    query[i].first = tr;
    Xs.push_back(tr.x);
    Ys.push_back(tr.y);

    cin >> x >> y;
    tr = transform45(x, y);
    query[i].second = tr;
    Xs.push_back(tr.x);
    Ys.push_back(tr.y);
  }

  sort(Xs.begin(), Xs.end());
  Xs.erase(unique(Xs.begin(), Xs.end()), Xs.end());
  sort(Ys.begin(), Ys.end());
  Ys.erase(unique(Ys.begin(), Ys.end()), Ys.end());

  for(int i = 0; i < N; ++i) {
    for(int k = 0; k < 4; ++k) {
      square[i][k].x = lower_bound(Xs.begin(), Xs.end(), square[i][k].x) - Xs.begin();
      square[i][k].y = lower_bound(Ys.begin(), Ys.end(), square[i][k].y) - Ys.begin();
    }
  }

  for(int i = 0; i < M; ++i) {
    query[i].first.x = lower_bound(Xs.begin(), Xs.end(), query[i].first.x) - Xs.begin();
    query[i].first.y = lower_bound(Ys.begin(), Ys.end(), query[i].first.y) - Ys.begin();
    query[i].second.x = lower_bound(Xs.begin(), Xs.end(), query[i].second.x) - Xs.begin();
    query[i].second.y = lower_bound(Ys.begin(), Ys.end(), query[i].second.y) - Ys.begin();
  }

#if 0
  cerr << "square" << endl;
  for(int i = 0; i < N; ++i) {
    cerr << i;
    for(int k = 0; k < 4; ++k) {
      cerr << " (" << square[i][k].x << ' ' << square[i][k].y << ")";
    }
    cerr << endl;
  }
  cerr << "query" << endl;
  for(int i = 0; i < M; ++i) {
    cerr << i;
    cerr << " (" << query[i].first.x << ' ' << query[i].first.y << ") ("
      << query[i].second.x << ' ' << query[i].second.y << ")" << endl;
  }
#endif

  vector<Event> event;
  for(int i = 0; i < N; ++i) {
    event.emplace_back(square[i][2].y, i, EventType::Add);
    event.emplace_back(square[i][0].y, i, EventType::Remove);
  }
  for(int i = 0; i < M; ++i) {
    event.emplace_back(query[i].first.y, i, EventType::Point);
    event.emplace_back(query[i].second.y, M + i, EventType::Point);
  }
  sort(event.begin(), event.end());

  BIT bit(Xs.size());
  bit.add(0, Xs.size() - 1, N);
  LCA lca(N + 1);
  vector<pair<int, int>> parent(M);
  for(const Event &e : event) {
    if(e.type == EventType::Add) {
      // cerr << e.y << " Add " << e.index << endl;
      pair<int, int> p = bit.successor(square[e.index][1].x, square[e.index][0].x);
      lca.add_edge(e.index, p.second);
      bit.add(square[e.index][1].x, square[e.index][0].x, e.index);
    }
    else if(e.type == EventType::Remove) {
      // cerr << e.y << " Remove " << e.index << endl;
      bit.remove(square[e.index][1].x, square[e.index][0].x, e.index);
    }
    else {
      // cerr << e.y << " Point " << (e.index < M ? e.index : e.index - M) << endl;
      int x;
      if(e.index < M) {
        x = query[e.index].first.x;
      }
      else {
        x = query[e.index - M].second.x;
      }
      pair<int, int> p = bit.successor(x, x);
      if(e.index < M) {
        parent[e.index].first = p.second;
      }
      else {
        parent[e.index - M].second = p.second;
      }
    }
  }

#if 0
  for(int i = 0; i < M; ++i) {
    cerr << parent[i].first << ' ' << parent[i].second << endl;
  }
  for(int i = 0; i < N + 1; ++i) {
    for(int j = 0; j < (int)lca.G[i].size(); ++j) {
      cerr << i << " <-> " << lca.G[i][j] << endl;
    }
  }
#endif

  lca.init(N);
  for(int i = 0; i < M; ++i) {
    int L = lca.lca(parent[i].first, parent[i].second);
    int result = 0;
    result += lca.depth[parent[i].first] - lca.depth[L];
    result += lca.depth[parent[i].second] - lca.depth[L];
    cout << result << endl;
  }
}

Submission Info

Judge Result