Submission #1173655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173655		avighna	Examination (JOI19_examination)	C++20	20 / 100	52 ms	4540 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});
  }
  std::sort(queries.begin(), queries.end(),
            [](Query a, Query b) { return a.x > b.x; });
  std::vector<int> ans(q);
  SegmentTree<int> st(int(1e5) + 1);
  for (auto &[x, y, z, i] : queries) {
    while (!a.empty() and a.back().first >= x) {
      st[a.back().second] += 1;
      a.pop_back();
    }
    ans[i] = st.query(y, int(1e5));
  }
  for (auto &i : ans) {
    std::cout << i << '\n';
  }
}

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