#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // #pragma GCC optimize("Ofast") // #pragma GCC target("avx,avx2,fma") // //#pragma GCC optimization ("O2") // #pragma GCC optimization ("unroll-loops") using namespace std; using namespace __gnu_pbds; typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define int long long #define ld long double #define ull unsigned long long #define mp make_pair // #define f first // #define s second #define INF 1000000000000000LL #define MOD 10000007 #define MOD_PHI 9988440 typedef pair<int, int> pi; typedef pair<pi, pi> pipi; typedef pair<int, pipi> ipipi; typedef pair<int, pi> ipi; typedef pair<pi, int> pii; typedef pair<int, char> pic; typedef pair<pic, int> spec; vector<int> s_pos; map<int, int> s_to_ind; struct node{ int s, e, m; int s_val; ordered_set vals; node *l, *r; node(int S, int E){ s = S, e = E, m = (s+e)/2; s_val = 0; if (s != e){ l = new node(s, m); r = new node(m+1, e); } } void upd(int X, int V, int P){ if(s == s_to_ind[X] and e == s_to_ind[X]){ // cout << "DBUG33 " << s << " " << e << endl; vals.insert(mp(V, P)); // for(auto it = vals.begin(); it != vals.end(); ++it) cout << (*it).first << " " << (*it).second << ", "; // cout << endl; return; } else { if (s_to_ind[X] <= m) l->upd(X, V, P); else r->upd(X, V, P); } vals.insert(mp(V, P)); } int qry(int S, int E, int V){ if(s > E or e < s) return 0; if(s == S and e == E){ // cout << "DEWBG " << s << " " << e << " " << vals.size() - vals.order_of_key(mp(V, -1)) << endl; // for(auto it = vals.begin(); it != vals.end(); ++it) cout << (*it).first << " " << (*it).second << ", "; // cout << endl; return vals.size() - vals.order_of_key(mp(V, -1)); } else if (E <= m){ return l->qry(S, E, V); } else if (S > m){ return r->qry(S, E, V); } else { return l->qry(S, m, V) + r->qry(m+1, E, V); } } } *root; bool cmp(pi a, pi b){ if(a.first + a.second < b.first + b.second) return true; else if (a.first + a.second == b.first + b.second){ if(a.first < b.first) return true; else return false; } return false; } void solve(){ int n, q; cin >> n >> q; vector<pi> stu; for(int i = 0; i < n; i++){ int x, y; cin >> x >> y; stu.push_back(mp(x, y)); s_pos.push_back(x); } sort(s_pos.begin(), s_pos.end()); sort(stu.begin(), stu.end(), cmp); s_pos.erase(unique(s_pos.begin(), s_pos.end()), s_pos.end()); for(int i = 0; i < s_pos.size(); i++){ s_to_ind[s_pos[i]] = i; } root = new node(0, s_pos.size()-1); int ans[q+1]; vector<pipi> queries; int cnt = 0; for(int i = 0; i < q; i++){ int x, y, z; cin >> x >> y >> z; queries.push_back(mp(mp(z, i), mp(x, y))); } sort(queries.begin(), queries.end()); while(not queries.empty()){ pipi curr_query = queries.back(); queries.pop_back(); while(not stu.empty() and stu.back().first + stu.back().second >= curr_query.first.first){ root->upd(stu.back().first, stu.back().second, stu.size()); //cout << "DB2: " << s_to_ind[stu.back().first] << " " << stu.back().second << " " << stu.size() << " " << curr_query.first.second << endl; stu.pop_back(); } int it = lower_bound(s_pos.begin(), s_pos.end(), curr_query.second.first)-s_pos.begin(); if(s_pos.size() == it) {ans[curr_query.first.second] = 0;} else{ ans[curr_query.first.second] = root->qry(it, s_pos.size()-1, curr_query.second.second); //cout << it << " " << s_pos.size()-1 << " " << curr_query.second.second << " " << ans[curr_query.first.second] << endl; } } for(int i = 0; i < q; i++) cout << ans[i] << '\n'; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc; //cin >> t; //int cnt = 1; tc = 1; //int ans = 0; while (tc--) { solve(); } //cout << ans << '\n'; }