Submission #956280

#	Time	Username	Problem	Language	Result	Execution time	Memory
956280		chrisvilches	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	2512 ms	3672 KiB

dragon2

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

struct Point {
  int x, y, idx;
  Point operator-(const Point& p) const { return {x - p.x, y - p.y, idx}; }
  Point operator+(const Point& p) const { return {x + p.x, y + p.y, idx}; }
  long long cross(const Point& p) const {
    return x * (long long)p.y - y * (long long)p.x;
  }

  Point negate() const { return {-x, -y, idx}; }
};

short orientation(const Point& o, const Point& a, const Point& b) {
  const long long x = (a - o).cross(b - o);
  return (x > 0) - (x < 0);
}

Point A, B;
vector<int> mid_it;

bool above(const Point& p) { return B.cross(p) > 0; }

Point to_upper(const Point& p) { return above(p) ? p : p.negate(); }
bool operator<(const Point& p, const Point& q) {
  return to_upper(p).cross(to_upper(q)) > 0;
}

bool cmp_by_b(const Point& p, const Point& q) {
  const bool a1 = above(p);
  const bool a2 = above(q);
  if (a1 != a2) return a1;
  return p.cross(q) > 0;
}

int query(const vector<Point>& points1, const vector<Point>& points2,
          const vector<Point>& ord_b, const int attacked_idx) {
  if (points1.empty() || points2.empty()) return 0;

  int total = 0;
  int events[]{0, 0};
  int j = 0;

  for (const Point& p : points1) {
    while (j < (int)points2.size()) {
      const Point& q = points2[j];

      if (p < q) break;

      events[above(q)]++;
      j++;
    }

    const auto mid = ord_b.begin() + mid_it[attacked_idx];

    if (above(p)) {
      const auto it = lower_bound(mid, ord_b.end(), B - p, cmp_by_b);

      const int count = it - mid;
      total += count - events[0];

      for (auto it = mid == ord_b.end() ? mid - 1 : mid;; it--) {
        const Point q = *it + B;
        total += above(q) && p.cross(q) < 0 && orientation(B, p, q) > 0;
        if (it == ord_b.begin()) break;
      }

    } else {
      const auto it = lower_bound(ord_b.begin(), mid, B - p, cmp_by_b);
      const int count = it - ord_b.begin();
      total += events[1] - count;

      for (auto it = mid; it != ord_b.end(); it++) {
        const Point q = *it + B;
        total += p.cross(q) > 0 && orientation(B, p, q) < 0;
      }
    }
  }

  return total;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, Q;

  while (cin >> N >> M) {
    vector<vector<Point>> tribe_points(M + 1);
    vector<vector<Point>> order_by_b(M + 1);
    mid_it.resize(M + 1);

    for (int i = 0; i < N; i++) {
      Point p;
      int tribe;
      cin >> p.x >> p.y >> tribe;
      tribe_points[tribe].push_back(p);
    }

    cin >> A.x >> A.y;
    cin >> B.x >> B.y;
    cin >> Q;
    B = B - A;

    for (int m = 0; m <= M; m++) {
      auto& points = tribe_points[m];
      for (auto& p : points) p = p - A;
      for (auto& p : points) p = p - B;
      sort(points.begin(), points.end(), cmp_by_b);
      for (int i = 0; i < (int)points.size(); i++) points[i].idx = i;
      auto& b = order_by_b[m];
      b = points;
      mid_it[m] = lower_bound(b.begin(), b.end(), B.negate(), cmp_by_b) - b.begin();
      for (auto& p : points) p = p + B;
      sort(points.begin(), points.end());
    }

    while (Q--) {
      int i, j;
      cin >> i >> j;
      cout << query(tribe_points[i], tribe_points[j], order_by_b[j], j) << '\n';
    }
  }
}

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