oj.uz

답안 #956895

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956895 2024-04-02T15:57:47 Z chrisvilches Dragon 2 (JOI17_dragon2) C++14
100 / 100
 774 ms 30044 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);
}

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

    if (attack) {
      ans[p.tribe][tribe_idx] += total;
    } else {
      ans[tribe_idx][p.tribe] += total;
    }
  }
}

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:86:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     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:96:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |   for (const auto& [_, tribe_idx, is_attack] : queries) {
      |                    ^
dragon2.cpp: In function 'int main()':
dragon2.cpp:165:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |     for (const auto& [i, j] : query_original_order) {
      |                      ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 612 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 32 ms 1484 KB Output is correct
4 Correct 153 ms 16220 KB Output is correct
5 Correct 133 ms 17180 KB Output is correct
6 Correct 3 ms 1624 KB Output is correct
7 Correct 3 ms 1880 KB Output is correct
8 Correct 2 ms 556 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

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 2456 KB Output is correct
2 Correct 60 ms 2932 KB Output is correct
3 Correct 21 ms 2396 KB Output is correct
4 Correct 12 ms 2396 KB Output is correct
5 Correct 14 ms 5724 KB Output is correct
6 Correct 16 ms 2544 KB Output is correct
7 Correct 15 ms 2396 KB Output is correct
8 Correct 16 ms 2392 KB Output is correct
9 Correct 12 ms 2272 KB Output is correct
10 Correct 12 ms 2264 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 612 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 32 ms 1484 KB Output is correct
4 Correct 153 ms 16220 KB Output is correct
5 Correct 133 ms 17180 KB Output is correct
6 Correct 3 ms 1624 KB Output is correct
7 Correct 3 ms 1880 KB Output is correct
8 Correct 2 ms 556 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 2456 KB Output is correct
12 Correct 60 ms 2932 KB Output is correct
13 Correct 21 ms 2396 KB Output is correct
14 Correct 12 ms 2396 KB Output is correct
15 Correct 14 ms 5724 KB Output is correct
16 Correct 16 ms 2544 KB Output is correct
17 Correct 15 ms 2396 KB Output is correct
18 Correct 16 ms 2392 KB Output is correct
19 Correct 12 ms 2272 KB Output is correct
20 Correct 12 ms 2264 KB Output is correct
21 Correct 19 ms 2392 KB Output is correct
22 Correct 61 ms 3000 KB Output is correct
23 Correct 478 ms 3948 KB Output is correct
24 Correct 774 ms 18212 KB Output is correct
25 Correct 195 ms 21444 KB Output is correct
26 Correct 244 ms 30044 KB Output is correct
27 Correct 30 ms 13272 KB Output is correct
28 Correct 30 ms 13100 KB Output is correct
29 Correct 221 ms 29520 KB Output is correct
30 Correct 253 ms 28372 KB Output is correct
31 Correct 255 ms 29512 KB Output is correct
32 Correct 246 ms 29636 KB Output is correct
33 Correct 517 ms 28484 KB Output is correct
34 Correct 212 ms 29564 KB Output is correct
35 Correct 268 ms 29772 KB Output is correct
36 Correct 206 ms 28660 KB Output is correct
37 Correct 205 ms 29768 KB Output is correct
38 Correct 521 ms 28752 KB Output is correct
39 Correct 547 ms 28672 KB Output is correct
40 Correct 574 ms 28556 KB Output is correct
41 Correct 215 ms 29244 KB Output is correct
42 Correct 230 ms 28952 KB Output is correct
43 Correct 246 ms 28868 KB Output is correct
44 Correct 38 ms 8084 KB Output is correct
45 Correct 32 ms 7912 KB Output is correct
46 Correct 32 ms 7784 KB Output is correct
47 Correct 33 ms 9424 KB Output is correct
48 Correct 39 ms 9432 KB Output is correct
49 Correct 34 ms 9352 KB Output is correct