#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define N 100001
pair<int, int> a[N];
oset<int> seg[4*N];
void build(int l, int r, int pos) {
for (int i = l; i <= r; i++)
seg[pos].insert(a[i].second);
if (l == r) return;
int mid = (l+r)/2;
build(l, mid, 2*pos);
build(mid+1, r, 2*pos+1);
}
int query(int qx, int qy, int l, int r, int pos) {
if (a[r].first < qx)
return 0;
if (a[l].first >= qx)
return seg[pos].order_of_key(qy-1);
int mid = (l+r)/2;
return query(qx, qy, l, mid, 2*pos) + query(qx, qy, mid+1, r, 2*pos+1);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i].first >> a[i].second;
sort(a+1, a+n+1);
build(1, n, 1);
while (q--) {
int x, y, z; cin >> x >> y >> z;
cout << query(x, y, 1, n, 1) << '\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... |