Submission #643497

#	Time	Username	Problem	Language	Result	Execution time	Memory
643497		lunchbox1	Dragon 2 (JOI17_dragon2)	C++17	100 / 100	1230 ms	17140 KiB

dragon2

/*
JOI17_dragon2 - Dragon 2

assume that |i|<|j| in the queries. notice that if you spend |i| per query,
then you get a O(n sqrt n) complexity
- if |i| less than sqrt n, then it's ok
- otherwise we have that both |i| (and |j|) are greater than sqrt n. there are
at most sqrt(n) j that are possible due to |j| so this amortizes to O(n sqrt n)

so for the geo part, we can write that the line crosses the village as a form 
of two inequalities (one for p and one for q).

you can use a 2d segtree (pst + binary search) to deal with this.

complexity is O(n sqrt n log n).
*/
#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);
  }
}

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