oj.uz

Submission #646304

# Submission time Handle Problem Language Result Execution time Memory
646304 2022-09-29T12:56:01 Z dnx04 Examination (JOI19_examination) C++17
20 / 100
 256 ms 12820 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 12316 KB Output is correct
2 Correct 205 ms 12252 KB Output is correct
3 Correct 256 ms 12344 KB Output is correct
4 Correct 165 ms 11592 KB Output is correct
5 Correct 156 ms 11568 KB Output is correct
6 Correct 131 ms 10800 KB Output is correct
7 Correct 200 ms 12292 KB Output is correct
8 Correct 192 ms 12244 KB Output is correct
9 Correct 189 ms 12196 KB Output is correct
10 Correct 151 ms 11344 KB Output is correct
11 Correct 189 ms 11344 KB Output is correct
12 Correct 150 ms 10436 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 12316 KB Output is correct
2 Correct 205 ms 12252 KB Output is correct
3 Correct 256 ms 12344 KB Output is correct
4 Correct 165 ms 11592 KB Output is correct
5 Correct 156 ms 11568 KB Output is correct
6 Correct 131 ms 10800 KB Output is correct
7 Correct 200 ms 12292 KB Output is correct
8 Correct 192 ms 12244 KB Output is correct
9 Correct 189 ms 12196 KB Output is correct
10 Correct 151 ms 11344 KB Output is correct
11 Correct 189 ms 11344 KB Output is correct
12 Correct 150 ms 10436 KB Output is correct
13 Incorrect 216 ms 12820 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -