oj.uz

Submission #1063513

# Submission time Handle Problem Language Result Execution time Memory
1063513 2024-08-17T19:44:10 Z nima_aryan Examination (JOI19_examination) C++17
0 / 100
 785 ms 69836 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);
  }

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

  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.size() - (lower_bound(xs.begin(), xs.end(), x) - xs.begin()) - 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 2388 KB Output is correct
8 Correct 8 ms 2140 KB Output is correct
9 Correct 8 ms 2188 KB Output is correct
10 Correct 7 ms 2392 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Incorrect 2 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 67468 KB Output is correct
2 Correct 783 ms 69832 KB Output is correct
3 Correct 772 ms 69836 KB Output is correct
4 Incorrect 545 ms 66664 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 67468 KB Output is correct
2 Correct 783 ms 69832 KB Output is correct
3 Correct 772 ms 69836 KB Output is correct
4 Incorrect 545 ms 66664 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 2388 KB Output is correct
8 Correct 8 ms 2140 KB Output is correct
9 Correct 8 ms 2188 KB Output is correct
10 Correct 7 ms 2392 KB Output is correct
11 Correct 4 ms 860 KB Output is correct
12 Incorrect 2 ms 604 KB Output isn't correct
13 Halted 0 ms 0 KB -