This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
namespace
{
template <typename T, typename Cmp = less<T>>
using OrderedSet = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;
} // namespace
void solve()
{
int n, q;
cin >> n >> q;
vector<array<long, 2>> a(n);
for (auto &[u, v] : a)
cin >> u >> v;
sort(
a.begin(), a.end(),
[&](const array<long, 2> &lhs, const array<long, 2> &rhs) -> bool
{ return lhs[0] + lhs[1] > rhs[0] + rhs[1]; });
vector<long> x(q), y(q), z(q);
for (int i = 0; i < q; i++)
cin >> x[i] >> y[i] >> z[i];
vector<long> all;
for (int i = 0; i < n; i++)
all.push_back(a[i][0]);
for (int i = 0; i < q; i++)
all.push_back(x[i]);
sort(all.begin(), all.end());
int k = (int)all.size();
auto idx = [&](long u) -> int
{ return (int)(lower_bound(all.begin(), all.end(), u) - all.begin()); };
vector<int> order(q);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(),
[&](int i, int j) -> bool
{ return z[i] > z[j]; });
vector<int> res(q);
vector<OrderedSet<pair<long, int>>> fenw(k + 1);
int op = 0;
auto upd = [&](long u, long v) -> void
{
for (int p = k - idx(u); p <= k; p += p & -p)
fenw[p].insert(pair(-v, op++));
};
auto qry = [&](long u, long v) -> int
{
int ret = 0;
for (int p = k - idx(u); p; p -= p & -p)
ret += (int)fenw[p].order_of_key(pair(-v, op));
return ret;
};
for (int l = 0, i = 0; i < q; i++)
{
int j = order[i];
while (l < n && a[l][0] + a[l][1] >= z[j])
{
upd(a[l][0], a[l][1]);
l++;
}
res[j] = qry(x[j], y[j]);
}
for (int i = 0; i < q; i++)
cout << res[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
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... |