oj.uz

Submission #646305

# Submission time Handle Problem Language Result Execution time Memory
646305 2022-09-29T12:59:40 Z dnx04 Examination (JOI19_examination) C++17
20 / 100
 235 ms 9900 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);

  auto sub2 = [&]() {  // correct
    for (auto &[s, t] : a) cin >> s >> t;
    for (int i = 0; i < q; ++i) {
      cin >> get<0>(query[i]) >> get<1>(query[i]) >> get<2>(query[i]);
      get<3>(query[i]) = i;
    }
    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<0>(query[i])) {
        s.insert({a[j].second, j});
        ++j;
      }
      auto it = s.order_of_key({get<1>(query[i]), -1});
      ans[get<3>(query[i])] = (int)s.size() - it;
    }
  };
  sub2();
  for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

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 204 ms 9820 KB Output is correct
2 Correct 235 ms 9816 KB Output is correct
3 Correct 199 ms 9832 KB Output is correct
4 Correct 169 ms 9852 KB Output is correct
5 Correct 171 ms 9816 KB Output is correct
6 Correct 127 ms 9752 KB Output is correct
7 Correct 206 ms 9840 KB Output is correct
8 Correct 191 ms 9812 KB Output is correct
9 Correct 215 ms 9900 KB Output is correct
10 Correct 148 ms 9816 KB Output is correct
11 Correct 188 ms 9660 KB Output is correct
12 Correct 155 ms 9428 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 9820 KB Output is correct
2 Correct 235 ms 9816 KB Output is correct
3 Correct 199 ms 9832 KB Output is correct
4 Correct 169 ms 9852 KB Output is correct
5 Correct 171 ms 9816 KB Output is correct
6 Correct 127 ms 9752 KB Output is correct
7 Correct 206 ms 9840 KB Output is correct
8 Correct 191 ms 9812 KB Output is correct
9 Correct 215 ms 9900 KB Output is correct
10 Correct 148 ms 9816 KB Output is correct
11 Correct 188 ms 9660 KB Output is correct
12 Correct 155 ms 9428 KB Output is correct
13 Incorrect 226 ms 9772 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 -