Submission #1063522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063522		nima_aryan	Examination (JOI19_examination)	C++17	100 / 100	869 ms	89832 KiB

examination

/**
 *    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 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57