Submission #956279

#	Time	Username	Problem	Language	Result	Execution time	Memory
956279		chrisvilches	Dragon 2 (JOI17_dragon2)	C++14	60 / 100	4054 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;

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;
}

const int bit_n = 30'001;
short bit[bit_n];

void clear(const int n) { memset(bit, 0, sizeof(short) * n); }

int sum(int r) {
  int ret = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
  return ret;
}

int sum(int l, int r) { return sum(r) - sum(l - 1); }

void add(int idx, const short delta) {
  for (; idx < bit_n; idx = idx | (idx + 1)) bit[idx] += delta;
}

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

  clear(points2.size());

  int total = 0;
  int j = 0;

  for (const auto& q : points2) {
    if (!above(q)) add(q.idx, 1);
  }

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

      if (p < q) break;
      add(q.idx, above(q) ? 1 : -1);

      j++;
    }

    Point from = p - B;
    Point to = B - p;

    if (!above(p)) swap(from, to);

    const int a = lower_bound(ord_b.begin(), ord_b.end(), from, cmp_by_b) - ord_b.begin();
    const int b = lower_bound(ord_b.begin(), ord_b.end(), to, cmp_by_b) - ord_b.begin();

    total += sum(a, b - 1);
  }

  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);

    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;
      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]) << '\n';
    }
  }
}

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