oj.uz

Submission #288865

# Submission time Handle Problem Language Result Execution time Memory
288865 2020-09-02T03:13:22 Z rama_pang Dragon 2 (JOI17_dragon2) C++14
60 / 100
 4000 ms 10488 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]--;
  }

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

  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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 75 ms 3648 KB Output is correct
5 Correct 48 ms 5040 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3584 KB Output is correct
2 Correct 54 ms 3580 KB Output is correct
3 Correct 31 ms 3616 KB Output is correct
4 Correct 26 ms 3704 KB Output is correct
5 Correct 28 ms 5112 KB Output is correct
6 Correct 26 ms 4352 KB Output is correct
7 Correct 26 ms 4344 KB Output is correct
8 Correct 26 ms 4344 KB Output is correct
9 Correct 19 ms 4088 KB Output is correct
10 Correct 22 ms 4096 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 25 ms 768 KB Output is correct
4 Correct 75 ms 3648 KB Output is correct
5 Correct 48 ms 5040 KB Output is correct
6 Correct 3 ms 1024 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 27 ms 3584 KB Output is correct
12 Correct 54 ms 3580 KB Output is correct
13 Correct 31 ms 3616 KB Output is correct
14 Correct 26 ms 3704 KB Output is correct
15 Correct 28 ms 5112 KB Output is correct
16 Correct 26 ms 4352 KB Output is correct
17 Correct 26 ms 4344 KB Output is correct
18 Correct 26 ms 4344 KB Output is correct
19 Correct 19 ms 4088 KB Output is correct
20 Correct 22 ms 4096 KB Output is correct
21 Correct 28 ms 4344 KB Output is correct
22 Correct 55 ms 4344 KB Output is correct
23 Correct 342 ms 4600 KB Output is correct
24 Correct 730 ms 8396 KB Output is correct
25 Correct 138 ms 9084 KB Output is correct
26 Correct 95 ms 10488 KB Output is correct
27 Correct 33 ms 6912 KB Output is correct
28 Correct 32 ms 6908 KB Output is correct
29 Execution timed out 4038 ms 9972 KB Time limit exceeded
30 Halted 0 ms 0 KB -