Submission #288869

#	Time	Username	Problem	Language	Result	Execution time	Memory
288869		rama_pang	Dragon 2 (JOI17_dragon2)	C++14	100 / 100	1004 ms	10872 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]--;
  }

  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);
  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);
  }
  for (int i = 0; i <= M; i++) {
    color_pos[i] = lower_bound(begin(sorted_y), end(sorted_y), make_pair(i, Y - X)) - begin(sorted_y);;
  }

  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]--, B[i]--;
    query_a[A[i]].emplace_back(B[i], i);
  }

  // O(N sqrt Q log N)
  const int SQRT = round(sqrt(Q));
  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();
    }
  }

  { // Solve query_a
    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);
      }
    }
  }

  { // Solve query_b
    Fenwick f0(N); // side[i] = true
    Fenwick f1(N); // side[i] = false
    for (int i = 0; i < N; i++) {
      f0.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_b[c]) {
        int pos = lower_bound(begin(sorted_y), end(sorted_y), make_pair(q.first, angle_y[i])) - begin(sorted_y);
        if (side[i]) {
          ans[q.second] += f0.Sum(color_pos[q.first], pos - 1);
        } else {
          ans[q.second] += f1.Sum(pos, color_pos[q.first + 1] - 1);
        }
      }
      f0.Update(pos_in_sorted[i], -1);
      f1.Update(pos_in_sorted[i], +1);
    }
  }

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

Compilation message (stderr)

dragon2.cpp: In function 'int main()':
dragon2.cpp:118:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
  118 |     if (query_a[i].size() >= SQRT) {
      |         ~~~~~~~~~~~~~~~~~~^~~~~~~

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