Submission #807705

#	Time	Username	Problem	Language	Result	Execution time	Memory
807705		dong_liu	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	1014 ms	17076 KiB

dragon2

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

template <class T>
pair<T, T> _minmax(const T& a, const T& b) {
  if (a < b)
    return make_pair(a, b);
  else
    return make_pair(b, a);
}

typedef __int128 i128;

const int N = 30000, Q = 100000;
const i128 PI = (i128)1e36 * acosl(-1);

i128 acos2_128(int x, int y) { return (i128)1e36 * atan2l(y, x); }
i128 opposite(const i128& x) { return x < 0 ? x + PI : x - PI; }

struct point {
  int x, y;
  i128 ang_a, ang_b;

  point() {}
  point(int x, int y) : x(x), y(y) {}
  i128 angle(const point& p) const { return acos2_128(p.x - x, p.y - y); }
} A, B;

int ans[Q];

namespace pst {
const int M = N * 15 * 2;
int sum[M], ll[M], rr[M], _;

void clear() { _ = 0; }
int node(int k = 0) {
  ++_;
  sum[_] = sum[k];
  ll[_] = ll[k], rr[_] = rr[k];
  return _;
}
int build(int l, int r) {
  int v = node(), m;

  if (l < r) {
    m = (l + r) / 2;
    ll[v] = build(l, m);
    rr[v] = build(m + 1, r);
  }
  return v;
}
int update(int v, int l, int r, int i, int x) {
  int v_ = node(v), m;

  sum[v_] += x;
  if (l < r) {
    m = (l + r) / 2;
    if (i <= m)
      ll[v_] = update(ll[v_], l, m, i, x);
    else
      rr[v_] = update(rr[v_], m + 1, r, i, x);
  }
  return v_;
}
int query(int v, int l, int r, int ql, int qr) {
  int m;

  if (qr < l || ql > r) return 0;
  if (ql <= l && qr >= r) return sum[v];
  m = (l + r) / 2;
  return query(ll[v], l, m, ql, qr) + query(rr[v], m + 1, r, ql, qr);
}
}  // namespace pst

struct group {
  vector<int> vv;
  vector<i128> xx, yy;
  vector<point> pp;
  int n;

  int size() { return n; }
  void add(const point& p) { pp.push_back(p), n++; }
  void add_query(const i128& lx, const i128& rx, const i128& ly, const i128& ry,
                 int h) {
    short l = lower_bound(yy.begin(), yy.end(), ly) - yy.begin();
    short r = upper_bound(yy.begin(), yy.end(), ry) - yy.begin() - 1;
    short l_ = lower_bound(xx.begin(), xx.end(), lx - 1) - xx.begin();
    short r_ = upper_bound(xx.begin(), xx.end(), rx) - xx.begin() - 1;

    ans[h] += pst::query(vv[r_ + 1], 0, yy.size() - 1, l, r) -
              pst::query(vv[l_], 0, yy.size() - 1, l, r);
  }
  void add1(const point& q, int h) {
    auto [l_a, r_a] = _minmax(q.ang_a, opposite(q.ang_a));
    bool side_a = l_a <= B.ang_a && B.ang_a <= r_a;
    auto [l_b, r_b] = _minmax(q.ang_b, opposite(q.ang_b));
    bool side_b = l_b <= A.ang_b && A.ang_b <= r_b;

    if (side_a == 1) {
      if (side_b == 1)
        add_query(l_a, r_a, l_b, r_b, h);
      else {
        add_query(l_a, r_a, -PI, l_b - 1, h);
        add_query(l_a, r_a, r_b + 1, PI, h);
      }
    } else {
      if (side_b == 1) {
        add_query(-PI, l_a - 1, l_b, r_b, h);
        add_query(r_a + 1, PI, l_b, r_b, h);
      } else {
        add_query(-PI, l_a - 1, -PI, l_b - 1, h);
        add_query(r_a + 1, PI, -PI, l_b - 1, h);
        add_query(-PI, l_a - 1, r_b + 1, PI, h);
        add_query(r_a + 1, PI, r_b + 1, PI, h);
      }
    }
  }
  void add2(const point& q, int h) {
    auto [l_a, r_a] = _minmax(q.ang_a, opposite(q.ang_a));
    bool side_a = !(l_a <= B.ang_a && B.ang_a <= r_a);
    auto [l_b, r_b] = _minmax(q.ang_b, opposite(q.ang_b));
    bool side_b = !(l_b <= A.ang_b && A.ang_b <= r_b);

    if (side_a == 1) {
      if (side_b == 1)
        add_query(l_a, r_a, l_b, r_b, h);
      else {
        add_query(l_a, r_a, -PI, l_b - 1, h);
        add_query(l_a, r_a, r_b + 1, PI, h);
      }
    } else {
      if (side_b == 1) {
        add_query(-PI, l_a - 1, l_b, r_b, h);
        add_query(r_a + 1, PI, l_b, r_b, h);
      } else {
        add_query(-PI, l_a - 1, -PI, l_b - 1, h);
        add_query(r_a + 1, PI, -PI, l_b - 1, h);
        add_query(-PI, l_a - 1, r_b + 1, PI, h);
        add_query(r_a + 1, PI, r_b + 1, PI, h);
      }
    }
    tie(l_a, r_a) = _minmax(opposite(q.ang_a), B.ang_a);
    side_a = !(l_a <= q.ang_a && q.ang_a <= r_a);
    tie(l_b, r_b) = _minmax(opposite(q.ang_b), A.ang_b);
    side_b = !(l_b <= q.ang_b && q.ang_b <= r_b);
    if (side_a == 1) {
      if (side_b == 1)
        add_query(l_a, r_a, l_b, r_b, h);
      else {
        add_query(l_a, r_a, -PI, l_b - 1, h);
        add_query(l_a, r_a, r_b + 1, PI, h);
      }
    } else {
      if (side_b == 1) {
        add_query(-PI, l_a - 1, l_b, r_b, h);
        add_query(r_a + 1, PI, l_b, r_b, h);
      } else {
        add_query(-PI, l_a - 1, -PI, l_b - 1, h);
        add_query(r_a + 1, PI, -PI, l_b - 1, h);
        add_query(-PI, l_a - 1, r_b + 1, PI, h);
        add_query(r_a + 1, PI, r_b + 1, PI, h);
      }
    }
  }
  void build() {
    for (const point& p : pp) {
      xx.push_back(p.ang_a);
      yy.push_back(p.ang_b);
    }
    sort(xx.begin(), xx.end());
    sort(yy.begin(), yy.end());
    sort(pp.begin(), pp.end(),
         [&](const point& p, const point& q) { return p.ang_a < q.ang_a; });
    pst::clear();
    vv.push_back(pst::build(0, yy.size() - 1));
    for (const point& p : pp) {
      int i = lower_bound(yy.begin(), yy.end(), p.ang_b) - yy.begin();

      vv.push_back(pst::update(vv.back(), 0, yy.size() - 1, i, +1));
    }
  }
  void clear() {
    xx.clear();
    yy.clear();
  }
} gr[N];

int main() {
#ifndef LOCAL
  ios::sync_with_stdio(false);
  cin.tie(NULL);
#endif
  static vector<tuple<int, int, bool>> todo[N];
  vector<pair<point, int>> pp;
  int n, m, q;

  cin >> n >> m;
  pp.resize(n);
  for (auto& [p, c] : pp) cin >> p.x >> p.y >> c, c--;
  cin >> A.x >> A.y >> B.x >> B.y;
  A.ang_a = A.angle(A);
  A.ang_b = B.angle(A);
  B.ang_a = A.angle(B);
  B.ang_b = B.angle(B);
  for (auto& [p, c] : pp) {
    p.ang_a = A.angle(p);
    p.ang_b = B.angle(p);
    gr[c].add(p);
  }
  pp.clear();
  cin >> q;
  for (int h = 0; h < q; h++) {
    int c1, c2;

    cin >> c1 >> c2, c1--, c2--;
    if (gr[c1].size() < gr[c2].size())
      todo[c2].push_back({c1, h, 0});
    else
      todo[c1].push_back({c2, h, 1});
  }
  for (int c = 0; c < m; c++) {
    gr[c].build();
    for (auto [c_, h, t] : todo[c])
      for (const point& p : gr[c_].pp)
        if (t == 0)
          gr[c].add1(p, h);
        else
          gr[c].add2(p, h);
    gr[c].clear();
    todo[c].clear();
  }
  for (int h = 0; h < q; h++) cout << ans[h] << '\n';
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40