Submission #646304

#	Time	Username	Problem	Language	Result	Execution time	Memory
646304		dnx04	Examination (JOI19_examination)	C++17	20 / 100	256 ms	12820 KiB

examination

#line 1 "Examination.cpp"
#include <bits/stdc++.h>

using namespace std;

#line 2 "algo/data-structure/pbds.hpp"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;  // find_by_order(), order_of_key()
template <typename TK>
using pbds_set = tree<TK, null_type, less<TK>, rb_tree_tag,
                      tree_order_statistics_node_update>;
template <typename TK, typename TV>
using pbds_map =
    tree<TK, TV, less<TK>, rb_tree_tag, tree_order_statistics_node_update>;
#line 6 "Examination.cpp"

signed main() {
  int n, q;
  cin >> n >> q;
  vector<pair<int, int>> a(n);
  vector<tuple<int, int, int, int>> query(q);
  vector<int> ans(n);
  for (auto &[s, t] : a) cin >> s >> t;
  for (int i = 0; i < q; ++i) {
    cin >> get<1>(query[i]) >> get<2>(query[i]) >> get<0>(query[i]);
    get<3>(query[i]) = i;
  }

  auto sub2 = [&]() {
    sort(a.rbegin(), a.rend());
    sort(query.rbegin(), query.rend());
    pbds_set<pair<int, int>> s;
    for (int i = 0, j = 0; i < q; ++i) {
      while (j < n && a[j].first >= get<1>(query[i])) {
        s.insert({a[j].second, j});
        ++j;
      }
      auto it = s.order_of_key({get<2>(query[i]), -1});
      ans[get<3>(query[i])] = (int)s.size() - it;
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
  };
  sub2();
}

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