#include <bits/stdc++.h> #define ll long long #define pb push_back #define eb emplace_back #define pu push #define ins insert #define fi first #define se second #define all(a) a.begin(),a.end() #define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fu(x,a,b) for (auto x=a;x<=b;x++) #define fd(x,a,b) for (auto x=a;x>=b;x--) #define int ll using namespace std; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); /* Competitive Programming notes that I need to study & fix my dumbass self: 1. Coding: - Always be sure to check the memory of arrays (maybe use vectors), for loops - Always try to maximize the memory if possible, even if you are going for subtasks - Do not exploit #define int long long, it will kill you 2. Stress: - Always try generating big testcases and try if they run 3. Time management: - Don't overcommit or undercommit, always spend a certain amount of time to think a problem, don't just look at it and say I'm fucked - Do not spend too much time coding brute-force solutions, they should be easily-codable solutions that don't take up too much time Time management schedule: Offline / LAH days (4 problems - 3h): 15' thinking of solution / idea 1. no idea: skip 2. yes idea: continue thinking for <= 15' + implementing: <= 20' + brute-force: <= 5' + test generator: <= 5' I hate offline because I am dumb */ typedef pair<int, int> ii; const int N = 3e5+5; const int B = 750; const int mod = 1e9+7; const int inf = 1e18; using cd = complex<double>; const long double PI = acos(-1); int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} int n,q, ans[N]; vector<array<int, 4>> event; bool cmp(array<int, 4> a, array<int, 4> b) { if (a[0] == b[0]) return a[3] < b[3]; return a[0] > b[0]; } int bit[N]; void update(int i, int val) { for (; i; i -= i & -i) bit[i] += val; } int get(int i) { int ret = 0; for (; i < N; i += i & -i) ret += bit[i]; return ret; } void cdq(int l, int r) { if (l >= r) return; // cout<<l<<" "<<r<<endl; int mid = l+r>>1; cdq(l, mid); cdq(mid+1, r); vector<array<int, 4>> ord; vector<int> rev; int i = l, j = mid+1; while (i <= mid && j <= r) { if (event[i][1] >= event[j][1]) { if (event[i][3] == -1) { update(event[i][2], 1); rev.pb(event[i][2]); } ord.pb(event[i]); i++; } else { if (event[j][3] != -1) ans[event[j][3]] += get(event[j][2]); ord.pb(event[j]); j++; } } while (i <= mid) { ord.pb(event[i]); // if (event[j][3] == -1) update(event[i][2], 1); i++; } while (j <= r) { ord.pb(event[j]); if (event[j][3] != -1) ans[event[j][3]] += get(event[j][2]); j++; } for (int i = l; i <= r; i++) event[i] = ord[i-l]; for (auto i : rev) update(i, -1); } void solve() { cin>>n>>q; vector<int> vc; for (int i = 0; i < n; i++) { int a,b; cin>>a>>b; event.pb({a, b, a+b, -1}); vc.pb(a+b); } for (int i = 0; i < q; i++) { int a,b,c; cin>>a>>b>>c; event.pb({a, b, c, i}); vc.pb(c); } sort(all(vc)); vc.erase(unique(all(vc)), vc.end()); for (auto& i : event) i[2] = lower_bound(all(vc), i[2]) - vc.begin() + 1; sort(all(event), cmp); // for (auto i : event) // { // for (int j = 0; j < 4; j++) cout<<i[j]<<" "; // cout<<endl; // } cdq(0, event.size()-1); for (int i = 0; i < q; i++) cout<<ans[i]<<endl; } /* Go through the mistakes you usually make and revise your code, for god's sake... */ signed main() { bruh //freopen("input.inp","r",stdin); //freopen("output.inp","w",stdout); int t = 1; // cin>>t; while (t--) { solve(); cout<<"\n"; } }