Submission #1173676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173676		avighna	Examination (JOI19_examination)	C++20	100 / 100	529 ms	48324 KiB

examination

#include <bits/stdc++.h>

template <typename T> class SegmentTree {
public:
  std::vector<T> seg;
  int n;

  SegmentTree(int n) : n(n) { seg.resize(2 * n); }

  void add(int idx, T del) {
    for (seg[idx += n] += del; idx > 1; idx /= 2) {
      seg[idx / 2] = seg[idx] + seg[idx ^ 1];
    }
  }

  T query(int l, int r) {
    T ans = 0;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        ans += seg[l++];
      }
      if (r & 1) {
        ans += seg[--r];
      }
    }
    return ans;
  }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n, q;
  std::cin >> n >> q;
  std::vector<std::pair<int, int>> a(n);
  std::vector<int> vals;
  for (auto &[s, t] : a) {
    std::cin >> s >> t;
    vals.push_back(s);
    vals.push_back(t);
    vals.push_back(s + t);
  }
  std::sort(a.begin(), a.end());
  struct Query {
    int x, y, z;
    int i;
  };
  std::vector<Query> queries;
  for (int i = 0, x, y, z; i < q; ++i) {
    std::cin >> x >> y >> z;
    queries.push_back({x, y, z, i});
    vals.push_back(x);
    vals.push_back(y);
    vals.push_back(x + y);
  }

  std::sort(vals.begin(), vals.end());
  std::map<int, int> compressed;
  int max = 0;
  for (auto &v : vals) {
    if (!compressed.contains(v)) {
      compressed[v] = max++;
    }
  }

  auto part = std::partition(queries.begin(), queries.end(),
                             [](Query q) { return q.x + q.y < q.z; });
  std::sort(part, queries.end(), [](Query a, Query b) { return a.x > b.x; });
  std::vector<int> ans(q);
  SegmentTree<int> st(max);
  int idx = a.size() - 1;
  for (auto it = part; it != queries.end(); ++it) {
    auto [x, y, z, i] = *it;
    while (idx >= 0 and a[idx].first >= x) {
      st.add(compressed[a[idx--].second], 1);
    }
    ans[i] = st.query(compressed[y], max - 1);
  }

  std::sort(queries.begin(), part, [](Query a, Query b) { return a.z > b.z; });
  std::sort(a.begin(), a.end(),
            [](std::pair<int, int> p1, std::pair<int, int> p2) {
              return p1.first + p1.second < p2.first + p2.second;
            });
  SegmentTree<int> st_x(max), st_y(max);
  idx = a.size() - 1;
  for (auto it = queries.begin(); it != part; ++it) {
    auto [x, y, z, i] = *it;
    while (idx >= 0 and a[idx].first + a[idx].second >= z) {
      st_x.add(compressed[a[idx].first], 1);
      st_y.add(compressed[a[idx--].second], 1);
    }
    int aub = a.size() - idx - 1;
    int a = st_x.query(compressed[x], max - 1);
    int b = st_y.query(compressed[y], max - 1);
    ans[i] = a + b - aub;
  }

  for (auto &i : ans) {
    std::cout << i << '\n';
  }
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57