oj.uz

Submission #956913

# Submission time Handle Problem Language Result Execution time Memory
956913 2024-04-02T16:27:18 Z chrisvilches Dragon 2 (JOI17_dragon2) C++14
100 / 100
 716 ms 28368 KB 
#include <bits/stdc++.h>
using namespace std;

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}; }
  bool ccw(const Point p) const { return (long long)x * p.y - (long long)y * p.x > 0; }
  Point negate() const { return {-x, -y, idx, tribe}; }
};

template <class T, unsigned int N>
struct BIT {
  void clear(const int n) { memset(bit, 0, sizeof(T) * n); }

  T sum(int l, int r) { return sum(r) - sum(l - 1); }

  void add(unsigned int idx, const T delta) {
    for (; idx < N; idx = idx | (idx + 1)) bit[idx] += delta;
  }

 private:
  T bit[N];

  T sum(int r) {
    T ret = 0;
    for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r];
    return ret;
  }
};

BIT<int, 30'001> bit;
Point A, B;
vector<unordered_map<int, int>> ans;
vector<vector<Point>> tribe_points, order_by_b;
int mid[30'001];

bool above(const Point p) { return B.ccw(p); }

Point to_upper(const Point p) { return above(p) ? p : p.negate(); }

bool operator<(const Point p, const Point q) { return to_upper(p).ccw(to_upper(q)); }

bool cmp(const Point p, const Point q) {
  return above(p) == above(q) ? p.ccw(q) : above(p);
}

// TODO: I think the last bool variable should be something like "single tribe attack"
//       That way it'd be clear as to what points are executing the attack.
void query(const vector<Point>& multi_tribes, const int tribe_idx, const bool attack) {
  const vector<Point>& single_tribe = tribe_points[tribe_idx];
  const vector<Point>& ord = order_by_b[tribe_idx];

  bit.clear(single_tribe.size());

  int j = 0;

  for (const Point p : multi_tribes) {
    while (j < (int)single_tribe.size() && single_tribe[j] < p) {
      bit.add(single_tribe[j++].idx, 1);
    }

    const int m = mid[tribe_idx];
    const int a = lower_bound(ord.begin(), ord.end(), p - B, cmp) - ord.begin();
    const int b = lower_bound(ord.begin(), ord.end(), B - p, cmp) - ord.begin();

    int& total = attack ? ans[p.tribe][tribe_idx] : ans[tribe_idx][p.tribe];

    total += above(p) ? b - m - bit.sum(m, b - 1) : bit.sum(0, m - 1) - b;

    if (attack) {
      total += above(p) ? bit.sum(a, m - 1) : a - m - bit.sum(m, a - 1);
    } else {
      total += above(p) ? a - bit.sum(0, a - 1) : bit.sum(a, ord.size() - 1);
    }
  }
}

void run_queries(const map<int, set<int>>& attacks, const map<int, set<int>>& attacked) {
  vector<tuple<long long, int, bool>> queries;

  const auto add_weighted_query = [&](const auto& q, const bool is_attack) {
    const auto [tribe_idx, other] = q;
    const long long weight = tribe_points[tribe_idx].size() * other.size();
    queries.emplace_back(weight, tribe_idx, is_attack);
  };

  for (const auto& q : attacks) add_weighted_query(q, true);
  for (const auto& q : attacked) add_weighted_query(q, false);

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

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

    const auto& other_tribes = (is_attack ? attacks : attacked).at(tribe_idx);

    for (const int other_tribe_idx : other_tribes) {
      int i = tribe_idx, j = other_tribe_idx;
      if (!is_attack) swap(i, j);

      if (ans[i].count(j)) continue;

      for (const Point p : tribe_points[other_tribe_idx]) {
        all_points.emplace_back(p);
      }

      ans[i][j] = 0;
    }

    sort(all_points.begin(), all_points.end());
    // TODO: should it be !is_attack or is_attack??? fix this and the variable name
    //       and usage in the "query" method.
    query(all_points, tribe_idx, !is_attack);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N, M, Q;

  while (cin >> N >> M) {
    tribe_points.assign(M + 1, vector<Point>());
    order_by_b.assign(M + 1, vector<Point>());
    ans.assign(M + 1, unordered_map<int, int>());

    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 >> B.x >> B.y;
    cin >> Q;
    B = B - A;

    for (int m = 1; m <= M; m++) {
      vector<Point>& points = tribe_points[m];
      for (Point& p : points) p = p - A;
      for (Point& p : points) p = p - B;
      sort(points.begin(), points.end(), cmp);
      for (int i = 0; i < (int)points.size(); i++) points[i].idx = i;
      order_by_b[m] = points;
      mid[m] = lower_bound(order_by_b[m].begin(), order_by_b[m].end(), B.negate(), cmp) -
               order_by_b[m].begin();
      for (Point& p : points) p = p + B;
      sort(points.begin(), points.end());
    }

    map<int, set<int>> attacks, attacked;
    vector<pair<int, int>> query_original_order;

    while (Q--) {
      int i, j;
      cin >> i >> j;
      attacks[i].emplace(j);
      attacked[j].emplace(i);
      query_original_order.emplace_back(i, j);
    }

    run_queries(attacks, attacked);

    for (const auto& [i, j] : query_original_order) {
      cout << ans[i][j] << '\n';
    }
  }
}

Compilation message

dragon2.cpp: In lambda function:
dragon2.cpp:83:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |     const auto [tribe_idx, other] = q;
      |                ^
dragon2.cpp: In function 'void run_queries(const std::map<int, std::set<int> >&, const std::map<int, std::set<int> >&)':
dragon2.cpp:93:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |   for (const auto& [_, tribe_idx, is_attack] : queries) {
      |                    ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:164:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  164 |     for (const auto& [i, j] : query_original_order) {
      |                      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 31 ms 1512 KB Output is correct
4 Correct 194 ms 15336 KB Output is correct
5 Correct 145 ms 16324 KB Output is correct
6 Correct 4 ms 1624 KB Output is correct
7 Correct 4 ms 1628 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1816 KB Output is correct
2 Correct 55 ms 2388 KB Output is correct
3 Correct 20 ms 1884 KB Output is correct
4 Correct 12 ms 1640 KB Output is correct
5 Correct 14 ms 5212 KB Output is correct
6 Correct 15 ms 1752 KB Output is correct
7 Correct 18 ms 2068 KB Output is correct
8 Correct 18 ms 1752 KB Output is correct
9 Correct 12 ms 1836 KB Output is correct
10 Correct 11 ms 1748 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 31 ms 1512 KB Output is correct
4 Correct 194 ms 15336 KB Output is correct
5 Correct 145 ms 16324 KB Output is correct
6 Correct 4 ms 1624 KB Output is correct
7 Correct 4 ms 1628 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 19 ms 1816 KB Output is correct
12 Correct 55 ms 2388 KB Output is correct
13 Correct 20 ms 1884 KB Output is correct
14 Correct 12 ms 1640 KB Output is correct
15 Correct 14 ms 5212 KB Output is correct
16 Correct 15 ms 1752 KB Output is correct
17 Correct 18 ms 2068 KB Output is correct
18 Correct 18 ms 1752 KB Output is correct
19 Correct 12 ms 1836 KB Output is correct
20 Correct 11 ms 1748 KB Output is correct
21 Correct 19 ms 1752 KB Output is correct
22 Correct 71 ms 2044 KB Output is correct
23 Correct 431 ms 3072 KB Output is correct
24 Correct 716 ms 16576 KB Output is correct
25 Correct 181 ms 19656 KB Output is correct
26 Correct 248 ms 27900 KB Output is correct
27 Correct 34 ms 12248 KB Output is correct
28 Correct 35 ms 12244 KB Output is correct
29 Correct 250 ms 28368 KB Output is correct
30 Correct 185 ms 26860 KB Output is correct
31 Correct 208 ms 27724 KB Output is correct
32 Correct 235 ms 28100 KB Output is correct
33 Correct 510 ms 27028 KB Output is correct
34 Correct 246 ms 27716 KB Output is correct
35 Correct 219 ms 28168 KB Output is correct
36 Correct 230 ms 27204 KB Output is correct
37 Correct 243 ms 27876 KB Output is correct
38 Correct 532 ms 27212 KB Output is correct
39 Correct 551 ms 27300 KB Output is correct
40 Correct 528 ms 26944 KB Output is correct
41 Correct 252 ms 27588 KB Output is correct
42 Correct 313 ms 27676 KB Output is correct
43 Correct 241 ms 27584 KB Output is correct
44 Correct 32 ms 7308 KB Output is correct
45 Correct 33 ms 7136 KB Output is correct
46 Correct 33 ms 7116 KB Output is correct
47 Correct 36 ms 8664 KB Output is correct
48 Correct 37 ms 8732 KB Output is correct
49 Correct 39 ms 8552 KB Output is correct