oj.uz

Submission #288853

# Submission time Handle Problem Language Result Execution time Memory
288853 2020-09-02T02:05:57 Z rama_pang Dragon 2 (JOI17_dragon2) C++14
0 / 100
 75 ms 6008 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 25 ms 896 KB Output is correct
4 Incorrect 75 ms 4472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4352 KB Output is correct
2 Correct 55 ms 4352 KB Output is correct
3 Correct 32 ms 4352 KB Output is correct
4 Correct 26 ms 4480 KB Output is correct
5 Incorrect 26 ms 6008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 25 ms 896 KB Output is correct
4 Incorrect 75 ms 4472 KB Output isn't correct
5 Halted 0 ms 0 KB -