This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* 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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |