oj.uz

Submission #1063522

# Submission time Handle Problem Language Result Execution time Memory
1063522 2024-08-17T19:53:21 Z nima_aryan Examination (JOI19_examination) C++17
100 / 100
 869 ms 89832 KB 
/**
 *    author:  NimaAryan
 *    created: 2024-08-17 22:57:42  
**/
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
template <typename T, class C = less<>>
using indexed_set = tree<T, null_type, C, rb_tree_tag,
      tree_order_statistics_node_update>;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

struct Solver {
  int n;
  vector<indexed_set<pair<int, int>>> a;

  Solver(int n) : n(n) {
    a.resize(n);
  }

  int tot = 0;

  void add(int x, int v) {
    ++tot;
    for (int i = x + 1; i <= n; i += i & -i) {
      a[i - 1].insert({v, tot});
    }
  }

  int query(int x, int v) {
    int res = 0;
    for (int i = x + 1; i > 0; i -= i & -i) {
      res += a[i - 1].size() - a[i - 1].order_of_key({v, 0});
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int N, Q;
  cin >> N >> Q;

  vector<int> S(N), T(N);
  for (int i = 0; i < N; ++i) {
    cin >> S[i] >> T[i];
  }

  vector<int> X(Q), Y(Q), Z(Q);
  for (int i = 0; i < Q; ++i) {
    cin >> X[i] >> Y[i] >> Z[i];
  }

  vector<int> p(Q);
  iota(p.begin(), p.end(), 0);
  sort(p.begin(), p.end(), [&](int i, int j) {
    return Z[i] > Z[j];
  });

  vector<int> q(N);
  iota(q.begin(), q.end(), 0);
  sort(q.begin(), q.end(), [&](int i, int j) {
    return S[i] + T[i] > S[j] + T[j];
  });

  auto xs = S;
  xs.insert(xs.end(), X.begin(), X.end());
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  auto id = [&](int x) {
    return xs.end() - lower_bound(xs.begin(), xs.end(), x) - 1;
  };

  vector<int> ans(Q);

  Solver f(xs.size());
  int x = 0;
  for (int i : p) {
    while (x < N && S[q[x]] + T[q[x]] >= Z[i]) {
      f.add(id(S[q[x]]), T[q[x]]);
      ++x;
    }
    ans[i] = f.query(id(X[i]), Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    cout << ans[i] << "\n";
  }

  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 7 ms 2140 KB Output is correct
9 Correct 8 ms 2140 KB Output is correct
10 Correct 7 ms 2216 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 7 ms 2456 KB Output is correct
14 Correct 8 ms 2392 KB Output is correct
15 Correct 7 ms 2504 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 6 ms 2396 KB Output is correct
18 Correct 2 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 67492 KB Output is correct
2 Correct 833 ms 67532 KB Output is correct
3 Correct 838 ms 67528 KB Output is correct
4 Correct 546 ms 67484 KB Output is correct
5 Correct 159 ms 20296 KB Output is correct
6 Correct 126 ms 19400 KB Output is correct
7 Correct 741 ms 70092 KB Output is correct
8 Correct 693 ms 69976 KB Output is correct
9 Correct 657 ms 70084 KB Output is correct
10 Correct 72 ms 12748 KB Output is correct
11 Correct 456 ms 68976 KB Output is correct
12 Correct 89 ms 11724 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 811 ms 67492 KB Output is correct
2 Correct 833 ms 67532 KB Output is correct
3 Correct 838 ms 67528 KB Output is correct
4 Correct 546 ms 67484 KB Output is correct
5 Correct 159 ms 20296 KB Output is correct
6 Correct 126 ms 19400 KB Output is correct
7 Correct 741 ms 70092 KB Output is correct
8 Correct 693 ms 69976 KB Output is correct
9 Correct 657 ms 70084 KB Output is correct
10 Correct 72 ms 12748 KB Output is correct
11 Correct 456 ms 68976 KB Output is correct
12 Correct 89 ms 11724 KB Output is correct
13 Correct 662 ms 70112 KB Output is correct
14 Correct 804 ms 70352 KB Output is correct
15 Correct 782 ms 69992 KB Output is correct
16 Correct 469 ms 69596 KB Output is correct
17 Correct 148 ms 20680 KB Output is correct
18 Correct 135 ms 19628 KB Output is correct
19 Correct 694 ms 70244 KB Output is correct
20 Correct 726 ms 70348 KB Output is correct
21 Correct 621 ms 70564 KB Output is correct
22 Correct 71 ms 12636 KB Output is correct
23 Correct 433 ms 69064 KB Output is correct
24 Correct 88 ms 11716 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 7 ms 2140 KB Output is correct
9 Correct 8 ms 2140 KB Output is correct
10 Correct 7 ms 2216 KB Output is correct
11 Correct 3 ms 856 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 7 ms 2456 KB Output is correct
14 Correct 8 ms 2392 KB Output is correct
15 Correct 7 ms 2504 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 6 ms 2396 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 811 ms 67492 KB Output is correct
20 Correct 833 ms 67532 KB Output is correct
21 Correct 838 ms 67528 KB Output is correct
22 Correct 546 ms 67484 KB Output is correct
23 Correct 159 ms 20296 KB Output is correct
24 Correct 126 ms 19400 KB Output is correct
25 Correct 741 ms 70092 KB Output is correct
26 Correct 693 ms 69976 KB Output is correct
27 Correct 657 ms 70084 KB Output is correct
28 Correct 72 ms 12748 KB Output is correct
29 Correct 456 ms 68976 KB Output is correct
30 Correct 89 ms 11724 KB Output is correct
31 Correct 662 ms 70112 KB Output is correct
32 Correct 804 ms 70352 KB Output is correct
33 Correct 782 ms 69992 KB Output is correct
34 Correct 469 ms 69596 KB Output is correct
35 Correct 148 ms 20680 KB Output is correct
36 Correct 135 ms 19628 KB Output is correct
37 Correct 694 ms 70244 KB Output is correct
38 Correct 726 ms 70348 KB Output is correct
39 Correct 621 ms 70564 KB Output is correct
40 Correct 71 ms 12636 KB Output is correct
41 Correct 433 ms 69064 KB Output is correct
42 Correct 88 ms 11716 KB Output is correct
43 Correct 707 ms 86660 KB Output is correct
44 Correct 711 ms 86760 KB Output is correct
45 Correct 869 ms 86476 KB Output is correct
46 Correct 490 ms 85192 KB Output is correct
47 Correct 156 ms 21704 KB Output is correct
48 Correct 113 ms 19400 KB Output is correct
49 Correct 808 ms 89832 KB Output is correct
50 Correct 614 ms 86452 KB Output is correct
51 Correct 668 ms 89804 KB Output is correct
52 Correct 123 ms 14252 KB Output is correct
53 Correct 439 ms 84240 KB Output is correct