Submission #1173669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173669		avighna	Examination (JOI19_examination)	C++20	20 / 100	62 ms	6076 KiB

examination

#include <bits/stdc++.h>

#include <functional>
#include <vector>

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

  class Ref {
    SegmentTree &st;
    int idx;

  public:
    Ref(SegmentTree &st, int idx) : st(st), idx(idx) {}
    operator T() const { return st.seg[idx + st.n]; }
    Ref &operator=(T x) {
      st.add(idx, x - st.seg[idx + st.n]);
      return *this;
    }
    Ref &operator+=(T del) {
      st.add(idx, del);
      return *this;
    }
  };
  Ref operator[](int idx) { return Ref(*this, idx); }
};

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);
  for (auto &[s, t] : a) {
    std::cin >> 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});
  }
  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(int(1e5) + 1);
  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[a[idx--].second] += 1;
    }
    ans[i] = st.query(y, int(1e5));
  }

  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(int(1e5) + 1), st_y(int(1e5) + 1);
  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[a[idx].first] += 1;
      st_y[a[idx--].second] += 1;
    }
    int aub = a.size() - idx - 1;
    int a = st_x.query(x, int(1e5));
    int b = st_y.query(y, int(1e5));
    ans[i] = a + b - aub;
  }

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

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