oj.uz

Submission #956728

# Submission time Handle Problem Language Result Execution time Memory
956728 2024-04-02T11:43:50 Z chrisvilches Dragon 2 (JOI17_dragon2) C++14
100 / 100
 962 ms 32992 KB 
#include <bits/stdc++.h>
using namespace std;

// Score: 60/100
// https://oj.uz/problem/view/JOI17_dragon2

struct Point {
  int x, y, idx, tribe;
  Point operator-(const Point& p) const { return {x - p.x, y - p.y, idx, tribe}; }
  Point operator+(const Point& p) const { return {x + p.x, y + p.y, idx, tribe}; }
  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, tribe}; }
};

// 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;
map<pair<int, int>, int> query_ans;

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

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

  clear(points2.size());

  int j = 0;

  for (const Point& p : points1) {
    int total = 0;

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

      if (p < q) break;
      add(q.idx, 1);

      j++;
    }

    const auto mid = lower_bound(ord_b.begin(), ord_b.end(), B.negate(), cmp_by_b);

    if (above(p)) {
      // TODO: "mid" is probably not necessary, since p is always "above",
      //       mid isn't touched, maybe?
      const auto it = lower_bound(ord_b.begin(), mid, p - B, cmp_by_b);
      const int idx = it - ord_b.begin();
      const int all = idx;
      const int enabled = sum(0, idx - 1);
      total += all - enabled;

      const auto it2 = lower_bound(mid, ord_b.end(), B - p, cmp_by_b);

      const int all_below = it2 - mid;
      const int enabled_below = sum(mid - ord_b.begin(), it2 - ord_b.begin() - 1);
      total += all_below - enabled_below;

    } else {
      auto it = lower_bound(ord_b.begin(), ord_b.end(), p - B, cmp_by_b);
      // TODO: What do you want? Is it necessary?
      // if (it != ord_b.end() && cmp_by_b(*it, p - B)) it++;
      if (it != ord_b.end()) {
        total += sum(it - ord_b.begin(), ord_b.size() - 1);
      }

      auto it2 = lower_bound(ord_b.begin(), mid, B - p, cmp_by_b);
      total += sum(it2 - ord_b.begin(), mid - ord_b.begin() - 1);
    }

    query_ans[{tribe_idx, p.tribe}] += total;
  }
}

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

  clear(points2.size());

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

    query_ans[{p.tribe, tribe_idx}] += sum(a, b - 1);
  }
}

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;
      cin >> p.x >> p.y >> p.tribe;
      tribe_points[p.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());
    }

    map<int, set<int>> attacks;
    map<int, set<int>> attacked;
    map<pair<int, int>, bool> query_done;
    vector<pair<int, int>> query_original_order;
    query_ans.clear();

    while (Q--) {
      int i, j;
      cin >> i >> j;
      attacks[i].emplace(j);
      attacked[j].emplace(i);
      query_original_order.emplace_back(i, j);
      // query(tribe_points[i], tribe_points[j], order_by_b[j], j);
      // query(tribe_points[i], tribe_points[j], order_by_b[j], j);
      // cout << query_ans[{i, j}] << '\n';
    }

    vector<tuple<long long, int, bool>> queries;
    for (const auto& [tribe_idx, other] : attacks) {
      // tribe_idx uses BIT
      const long long bit_weight = tribe_points[tribe_idx].size() * other.size();
      queries.emplace_back(bit_weight, tribe_idx, true);
    }
    for (const auto& [tribe_idx, other] : attacked) {
      // tribe_idx uses BIT
      const long long bit_weight = tribe_points[tribe_idx].size() * other.size();
      queries.emplace_back(bit_weight, tribe_idx, false);
    }

    sort(queries.rbegin(), queries.rend());

    set<pair<int, int>> visited;

    for (const auto& [_, tribe_idx, is_attack] : queries) {
      vector<Point> all;

      if (is_attack) {
        for (const int other_tribe_idx : attacks[tribe_idx]) {
          const pair<int, int> query_pair{tribe_idx, other_tribe_idx};
          if (visited.count(query_pair)) continue;

          for (const Point& p : tribe_points[other_tribe_idx]) all.emplace_back(p);
          visited.emplace(query_pair);
        }
      } else {
        for (const int other_tribe_idx : attacked[tribe_idx]) {
          const pair<int, int> query_pair{other_tribe_idx, tribe_idx};
          if (visited.count(query_pair)) continue;

          for (const Point& p : tribe_points[other_tribe_idx]) all.emplace_back(p);
          visited.emplace(query_pair);
        }
      }

      sort(all.begin(), all.end());

      if (is_attack) {
        query_attacked_by(all, tribe_points[tribe_idx], order_by_b[tribe_idx], tribe_idx);
      } else {
        query(all, tribe_points[tribe_idx], order_by_b[tribe_idx], tribe_idx);
      }
    }

    // cerr << "--" << rand() << endl;
    for (const auto& [i, j] : query_original_order) {
      const int ans = query_ans[{i, j}];
      cout << ans << '\n';
    }
  }
}

Compilation message

dragon2.cpp: In function 'int main()':
dragon2.cpp:194:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  194 |     for (const auto& [tribe_idx, other] : attacks) {
      |                      ^
dragon2.cpp:199:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  199 |     for (const auto& [tribe_idx, other] : attacked) {
      |                      ^
dragon2.cpp:209:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  209 |     for (const auto& [_, tribe_idx, is_attack] : queries) {
      |                      ^
dragon2.cpp:240:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  240 |     for (const auto& [i, j] : query_original_order) {
      |                      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 36 ms 1624 KB Output is correct
4 Correct 229 ms 23040 KB Output is correct
5 Correct 206 ms 23704 KB Output is correct
6 Correct 3 ms 1368 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 556 KB Output is correct
10 Correct 2 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2452 KB Output is correct
2 Correct 57 ms 2932 KB Output is correct
3 Correct 20 ms 2396 KB Output is correct
4 Correct 11 ms 2436 KB Output is correct
5 Correct 12 ms 4188 KB Output is correct
6 Correct 15 ms 2396 KB Output is correct
7 Correct 14 ms 2396 KB Output is correct
8 Correct 15 ms 2388 KB Output is correct
9 Correct 11 ms 2268 KB Output is correct
10 Correct 11 ms 2264 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 36 ms 1624 KB Output is correct
4 Correct 229 ms 23040 KB Output is correct
5 Correct 206 ms 23704 KB Output is correct
6 Correct 3 ms 1368 KB Output is correct
7 Correct 4 ms 1372 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 556 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 20 ms 2452 KB Output is correct
12 Correct 57 ms 2932 KB Output is correct
13 Correct 20 ms 2396 KB Output is correct
14 Correct 11 ms 2436 KB Output is correct
15 Correct 12 ms 4188 KB Output is correct
16 Correct 15 ms 2396 KB Output is correct
17 Correct 14 ms 2396 KB Output is correct
18 Correct 15 ms 2388 KB Output is correct
19 Correct 11 ms 2268 KB Output is correct
20 Correct 11 ms 2264 KB Output is correct
21 Correct 18 ms 2380 KB Output is correct
22 Correct 61 ms 2752 KB Output is correct
23 Correct 459 ms 3972 KB Output is correct
24 Correct 962 ms 24968 KB Output is correct
25 Correct 274 ms 27688 KB Output is correct
26 Correct 250 ms 32844 KB Output is correct
27 Correct 32 ms 11220 KB Output is correct
28 Correct 33 ms 11192 KB Output is correct
29 Correct 251 ms 32756 KB Output is correct
30 Correct 222 ms 31584 KB Output is correct
31 Correct 236 ms 32596 KB Output is correct
32 Correct 259 ms 32692 KB Output is correct
33 Correct 572 ms 31812 KB Output is correct
34 Correct 248 ms 32832 KB Output is correct
35 Correct 234 ms 32816 KB Output is correct
36 Correct 288 ms 31812 KB Output is correct
37 Correct 307 ms 32992 KB Output is correct
38 Correct 585 ms 32044 KB Output is correct
39 Correct 641 ms 31792 KB Output is correct
40 Correct 620 ms 31920 KB Output is correct
41 Correct 262 ms 32312 KB Output is correct
42 Correct 258 ms 32060 KB Output is correct
43 Correct 308 ms 31984 KB Output is correct
44 Correct 36 ms 8156 KB Output is correct
45 Correct 36 ms 8152 KB Output is correct
46 Correct 35 ms 8068 KB Output is correct
47 Correct 37 ms 7904 KB Output is correct
48 Correct 36 ms 7884 KB Output is correct
49 Correct 36 ms 8068 KB Output is correct