oj.uz

Submission #894219

# Submission time Handle Problem Language Result Execution time Memory
894219 2023-12-28T02:57:42 Z box Dragon 2 (JOI17_dragon2) C++17
100 / 100
 1027 ms 18740 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6236 KB Output is correct
2 Correct 19 ms 5980 KB Output is correct
3 Correct 52 ms 6240 KB Output is correct
4 Correct 54 ms 9008 KB Output is correct
5 Correct 31 ms 9364 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Correct 4 ms 6240 KB Output is correct
8 Correct 4 ms 6232 KB Output is correct
9 Correct 3 ms 5960 KB Output is correct
10 Correct 4 ms 5980 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14180 KB Output is correct
2 Correct 172 ms 11216 KB Output is correct
3 Correct 43 ms 12116 KB Output is correct
4 Correct 22 ms 11532 KB Output is correct
5 Correct 23 ms 12388 KB Output is correct
6 Correct 47 ms 14292 KB Output is correct
7 Correct 40 ms 14148 KB Output is correct
8 Correct 38 ms 14404 KB Output is correct
9 Correct 24 ms 14164 KB Output is correct
10 Correct 28 ms 14152 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6236 KB Output is correct
2 Correct 19 ms 5980 KB Output is correct
3 Correct 52 ms 6240 KB Output is correct
4 Correct 54 ms 9008 KB Output is correct
5 Correct 31 ms 9364 KB Output is correct
6 Correct 5 ms 6236 KB Output is correct
7 Correct 4 ms 6240 KB Output is correct
8 Correct 4 ms 6232 KB Output is correct
9 Correct 3 ms 5960 KB Output is correct
10 Correct 4 ms 5980 KB Output is correct
11 Correct 49 ms 14180 KB Output is correct
12 Correct 172 ms 11216 KB Output is correct
13 Correct 43 ms 12116 KB Output is correct
14 Correct 22 ms 11532 KB Output is correct
15 Correct 23 ms 12388 KB Output is correct
16 Correct 47 ms 14292 KB Output is correct
17 Correct 40 ms 14148 KB Output is correct
18 Correct 38 ms 14404 KB Output is correct
19 Correct 24 ms 14164 KB Output is correct
20 Correct 28 ms 14152 KB Output is correct
21 Correct 48 ms 14356 KB Output is correct
22 Correct 165 ms 11168 KB Output is correct
23 Correct 1027 ms 12092 KB Output is correct
24 Correct 1016 ms 14876 KB Output is correct
25 Correct 94 ms 15176 KB Output is correct
26 Correct 66 ms 15948 KB Output is correct
27 Correct 26 ms 13332 KB Output is correct
28 Correct 28 ms 13336 KB Output is correct
29 Correct 91 ms 18512 KB Output is correct
30 Correct 75 ms 18532 KB Output is correct
31 Correct 60 ms 18740 KB Output is correct
32 Correct 76 ms 15916 KB Output is correct
33 Correct 644 ms 16188 KB Output is correct
34 Correct 55 ms 16212 KB Output is correct
35 Correct 60 ms 15696 KB Output is correct
36 Correct 66 ms 15732 KB Output is correct
37 Correct 67 ms 15980 KB Output is correct
38 Correct 685 ms 16248 KB Output is correct
39 Correct 875 ms 15764 KB Output is correct
40 Correct 754 ms 15952 KB Output is correct
41 Correct 123 ms 17908 KB Output is correct
42 Correct 161 ms 15584 KB Output is correct
43 Correct 225 ms 15276 KB Output is correct
44 Correct 71 ms 15080 KB Output is correct
45 Correct 60 ms 14660 KB Output is correct
46 Correct 62 ms 12592 KB Output is correct
47 Correct 52 ms 15116 KB Output is correct
48 Correct 53 ms 14584 KB Output is correct
49 Correct 47 ms 12504 KB Output is correct