제출 #288853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288853		rama_pang	Dragon 2 (JOI17_dragon2)	C++14	0 / 100	75 ms	6008 KiB

dragon2

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

using Point = complex<long long>;

long long Dot(Point a, Point b) {
  return real(conj(a) * b);
}
long long Cross(Point a, Point b) {
  return imag(conj(a) * b);
}
bool Clockwise(Point a, Point b, Point c) {
  return Cross(b - a, c - a) > 0;
}
bool CounterClockwise(Point a, Point b, Point c) {
  return Cross(b - a, c - a) < 0;
}

namespace std {

template<class T>
istream& operator>>(istream &is, complex<T> &inp) {
  T a, b;
  is >> a >> b;
  inp = complex<T>(a, b);
  return is;
}

bool operator<(Point p, Point q) {
  return Cross(p, q) > 0;
}

}

class Fenwick {
 public:
  int sz;
  vector<int> tree;

  Fenwick() {}
  Fenwick(int sz) : sz(sz), tree(sz) {}

  void Update(int p, int x) {
    for (int i = p; i < sz; i |= i + 1) {
      tree[i] += x;
    }
  }
  int Sum(int p) {
    int res = 0;
    for (int i = p + 1; i > 0; i &= i - 1) {
      res += tree[i - 1];
    }
    return res;
  }
  int Sum(int l, int r) {
    return Sum(r) - Sum(l - 1);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  int N, M;
  cin >> N >> M;

  vector<int> C(N);
  vector<Point> P(N);
  for (int i = 0; i < N; i++) {
    cin >> P[i] >> C[i];
    C[i] -= 1;
  }

  Point X, Y;
  cin >> X >> Y;

  vector<bool> side(N);
  for (int i = 0; i < N; i++) {
    side[i] = Clockwise(X, Y, P[i]);
  }

  vector<Point> angle_x(N), angle_y(N);
  vector<pair<Point, int>> sorted_x(N);
  vector<pair<int, Point>> sorted_y(N);
  for (int i = 0; i < N; i++) {
    angle_x[i] = (side[i] ? P[i] - X : X - P[i]);
    sorted_x[i] = make_pair(angle_x[i], i);
    
    angle_y[i] = (side[i] ? P[i] - Y : Y - P[i]);
    sorted_y[i] = make_pair(C[i], angle_y[i]);
  }
  sort(begin(sorted_x), end(sorted_x));
  sort(begin(sorted_y), end(sorted_y));

  vector<int> pos_in_sorted(N), color_pos(M + 1, sorted_y.size());
  for (int i = 0; i < N; i++) {
    pos_in_sorted[i] = lower_bound(begin(sorted_y), end(sorted_y), make_pair(C[i], angle_y[i])) - begin(sorted_y);
    color_pos[C[i]] = min(color_pos[C[i]], pos_in_sorted[i]);
  }

  int Q;
  cin >> Q;
  vector<int> A(Q), B(Q);
  vector<long long> ans(Q);
  vector<vector<pair<int, int>>> query_a(M);
  vector<vector<pair<int, int>>> query_b(M);
  for (int i = 0; i < Q; i++) {
    cin >> A[i] >> B[i];
    A[i] -= 1;
    B[i] -= 1;
    query_a[A[i]].emplace_back(B[i], i);
  }

  const int SQRT = 200000;  
  for (int i = 0; i < M; i++) {
    if (query_a[i].size() >= SQRT) {
      for (auto j : query_a[i]) {
        query_b[j.first].emplace_back(i, j.second);
      }
      query_a[i].clear();
    }
  }

  Fenwick f0(N); // side[i] = true
  Fenwick f1(N); // side[i] = false
  for (int i = 0; i < N; i++) {
    if (!side[i]) {
      f1.Update(pos_in_sorted[i], +1);
    }
  }
  for (int t = 0; t < N; t++) {
    int i = sorted_x[t].second;
    int c = C[i];
    for (auto q : query_a[c]) {
      int pos = lower_bound(begin(sorted_y), end(sorted_y), make_pair(q.first, angle_y[i])) - begin(sorted_y);
      ans[q.second] += f0.Sum(pos, color_pos[q.first + 1] - 1);
      ans[q.second] += f1.Sum(color_pos[q.first], pos - 1);
    }
    if (side[i]) {
      f0.Update(pos_in_sorted[i], +1);
    } else {
      f1.Update(pos_in_sorted[i], -1);
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << ans[i] << '\n';
  }
  return 0;
}

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