oj.uz

Submission #956903

# Submission time Handle Problem Language Result Execution time Memory
956903 2024-04-02T16:05:41 Z chrisvilches Dragon 2 (JOI17_dragon2) C++14
100 / 100
 761 ms 28100 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;

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) {
      const Point q = single_tribe[j];
      bit.add(q.idx, 1);
      j++;
    }

    const int m = lower_bound(ord.begin(), ord.end(), B.negate(), cmp) - ord.begin();
    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;
      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:84:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     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:94:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |   for (const auto& [_, tribe_idx, is_attack] : queries) {
      |                    ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:163:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |     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 604 KB Output is correct
3 Correct 31 ms 1372 KB Output is correct
4 Correct 165 ms 15264 KB Output is correct
5 Correct 138 ms 16328 KB Output is correct
6 Correct 3 ms 1628 KB Output is correct
7 Correct 3 ms 1628 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 1 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 21 ms 1816 KB Output is correct
2 Correct 59 ms 2260 KB Output is correct
3 Correct 20 ms 1880 KB Output is correct
4 Correct 12 ms 1624 KB Output is correct
5 Correct 14 ms 5004 KB Output is correct
6 Correct 17 ms 1880 KB Output is correct
7 Correct 15 ms 1856 KB Output is correct
8 Correct 16 ms 1752 KB Output is correct
9 Correct 15 ms 1760 KB Output is correct
10 Correct 12 ms 1752 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 604 KB Output is correct
3 Correct 31 ms 1372 KB Output is correct
4 Correct 165 ms 15264 KB Output is correct
5 Correct 138 ms 16328 KB Output is correct
6 Correct 3 ms 1628 KB Output is correct
7 Correct 3 ms 1628 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 21 ms 1816 KB Output is correct
12 Correct 59 ms 2260 KB Output is correct
13 Correct 20 ms 1880 KB Output is correct
14 Correct 12 ms 1624 KB Output is correct
15 Correct 14 ms 5004 KB Output is correct
16 Correct 17 ms 1880 KB Output is correct
17 Correct 15 ms 1856 KB Output is correct
18 Correct 16 ms 1752 KB Output is correct
19 Correct 15 ms 1760 KB Output is correct
20 Correct 12 ms 1752 KB Output is correct
21 Correct 19 ms 1752 KB Output is correct
22 Correct 60 ms 2224 KB Output is correct
23 Correct 428 ms 3108 KB Output is correct
24 Correct 761 ms 16636 KB Output is correct
25 Correct 203 ms 19652 KB Output is correct
26 Correct 236 ms 27720 KB Output is correct
27 Correct 32 ms 12308 KB Output is correct
28 Correct 40 ms 12196 KB Output is correct
29 Correct 232 ms 27896 KB Output is correct
30 Correct 192 ms 26688 KB Output is correct
31 Correct 233 ms 27876 KB Output is correct
32 Correct 217 ms 28100 KB Output is correct
33 Correct 520 ms 26816 KB Output is correct
34 Correct 267 ms 27716 KB Output is correct
35 Correct 257 ms 28100 KB Output is correct
36 Correct 212 ms 26948 KB Output is correct
37 Correct 214 ms 27716 KB Output is correct
38 Correct 525 ms 27340 KB Output is correct
39 Correct 556 ms 27176 KB Output is correct
40 Correct 536 ms 26816 KB Output is correct
41 Correct 240 ms 27592 KB Output is correct
42 Correct 272 ms 27420 KB Output is correct
43 Correct 291 ms 27336 KB Output is correct
44 Correct 34 ms 7320 KB Output is correct
45 Correct 34 ms 7136 KB Output is correct
46 Correct 34 ms 7044 KB Output is correct
47 Correct 36 ms 8656 KB Output is correct
48 Correct 36 ms 8656 KB Output is correct
49 Correct 38 ms 8592 KB Output is correct