#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Point {
int s;
int t_idx; // compressed index of T in allV (1-based)
ll w; // s + t
int t_orig; // original T (not strictly needed)
};
struct Query {
int X;
int Y;
ll Z;
int idx; // original index
int y_idx; // compressed index of Y in allV (1-based)
};
struct FenwickSimple {
// 1-indexed Fenwick for integers
int n;
vector<int> bit;
FenwickSimple() {}
FenwickSimple(int n_): n(n_), bit(n_+1, 0) {}
void add(int i, int delta) {
for (; i <= n; i += i & -i) bit[i] += delta;
}
int sumPrefix(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
if (!(cin >> N >> Q)) return 0;
vector<pair<int,int>> pts(N);
for (int i = 0; i < N; ++i) cin >> pts[i].first >> pts[i].second;
vector<tuple<int,int,ll>> queries_input(Q);
vector<Query> queries(Q);
for (int j = 0; j < Q; ++j) {
int X, Y;
long long Z;
cin >> X >> Y >> Z;
queries_input[j] = {X, Y, Z};
queries[j].X = X;
queries[j].Y = Y;
queries[j].Z = Z;
queries[j].idx = j;
}
// 1) coordinate compress all T's and all Y's
vector<int> allV;
allV.reserve(N + Q);
for (int i = 0; i < N; ++i) allV.push_back(pts[i].second);
for (int j = 0; j < Q; ++j) allV.push_back(queries[j].Y);
sort(allV.begin(), allV.end());
allV.erase(unique(allV.begin(), allV.end()), allV.end());
int M = (int)allV.size();
// Build Points with compressed t_idx and w
vector<Point> points(N);
for (int i = 0; i < N; ++i) {
int s = pts[i].first;
int t = pts[i].second;
int t_idx = int(lower_bound(allV.begin(), allV.end(), t) - allV.begin()) + 1; // 1-based
points[i].s = s;
points[i].t_idx = t_idx;
points[i].w = (ll)s + (ll)t;
points[i].t_orig = t;
}
// set y_idx for queries (first index with value >= Y)
for (int j = 0; j < Q; ++j) {
int Y = queries[j].Y;
int y_idx = int(lower_bound(allV.begin(), allV.end(), Y) - allV.begin()) + 1; // 1-based
// if Y is greater than all values, y_idx will be M+1. That's OK.
queries[j].y_idx = y_idx;
}
// 2) Prepare bit nodes: for each point, push w into nodes i = t_idx .. M stepping by i&-i
vector<vector<ll>> node_vals(M+1);
for (int i = 0; i < N; ++i) {
int idx = points[i].t_idx;
ll w = points[i].w;
for (int p = idx; p <= M; p += p & -p) node_vals[p].push_back(w);
}
// sort & unique each node's values and prepare FenwickSimple for each node
vector<FenwickSimple> node_bit(M+1);
vector<int> node_total(M+1, 0); // number of inserts done in that node
for (int i = 1; i <= M; ++i) {
auto &v = node_vals[i];
if (!v.empty()) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
node_bit[i] = FenwickSimple((int)v.size());
}
}
// 3) Sort points by s descending and queries by X descending
sort(points.begin(), points.end(), [](const Point &a, const Point &b){
return a.s > b.s;
});
sort(queries.begin(), queries.end(), [](const Query &a, const Query &b){
return a.X > b.X;
});
// helper functions: update a point (t_idx, w) into BIT-of-v
auto update_point = [&](int t_idx, ll w) {
for (int p = t_idx; p <= M; p += p & -p) {
auto &vals = node_vals[p];
if (vals.empty()) continue;
int pos = int(lower_bound(vals.begin(), vals.end(), w) - vals.begin()); // 0-based
// update FenwickSimple at pos+1 by +1
node_bit[p].add(pos+1, 1);
node_total[p] += 1;
}
};
// query prefix up to idx (v <= idx), count w >= Z
auto query_prefix = [&](int idx, ll Z) -> int {
if (idx <= 0) return 0;
if (idx > M) idx = M;
int res = 0;
for (int p = idx; p > 0; p -= p & -p) {
auto &vals = node_vals[p];
if (vals.empty()) continue;
int pos = int(lower_bound(vals.begin(), vals.end(), Z) - vals.begin()); // number of values < Z
int pref = node_bit[p].sumPrefix(pos); // count of w < Z
// suffix = total - pref = count of w >= Z
res += (node_total[p] - pref);
}
return res;
};
vector<int> ans(Q, 0);
int cur_pt = 0; // index in points (sorted desc by s)
for (int qi = 0; qi < Q; ++qi) {
const Query &q = queries[qi];
int X = q.X;
// insert all points with s >= X
while (cur_pt < N && points[cur_pt].s >= X) {
update_point(points[cur_pt].t_idx, points[cur_pt].w);
++cur_pt;
}
int y_idx = q.y_idx;
// if y_idx is M+1 (Y greater than any compressed value), then no v >= Y exists -> answer 0
if (y_idx > M) {
ans[q.idx] = 0;
continue;
}
int total_up_to_M = query_prefix(M, q.Z);
int up_to_before_y = query_prefix(y_idx - 1, q.Z);
ans[q.idx] = total_up_to_M - up_to_before_y;
}
// print answers in original order
for (int j = 0; j < Q; ++j) cout << ans[j] << '\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... |