#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define all(x) x.begin(),x.end()
#define pb push_back
#define Mp make_pair
#define for1(n) for(int i=1;i<=n;i++)
#define for0(n) for(int i=0;i<n;i++)
#define set_dec(x) cout << fixed << setprecision(x);
#define endl '\n'
#define lb lower_bound
const int N=1e5+10;
int n,m,k,q,ans[N];
vector<int>vec;
vector<pii>ad[N*6];
vector<pair<pii,int>>Q[N*6];
pii A[N];
pair<pii,int>B[N];
int fen[2][N*6],num;
int gt(int x){
return lb(all(vec),x)-vec.begin();
}
void upd(int i,int x,int t){
for(;i<N;i+=i&-i)fen[t][i]+=x;
}
int get(int i,int t){
int ans=0;
for(;i>0;i-=i&-i)ans+=fen[t][i];
return ans;
}
int main(){
fast_io
vec.pb(-1);
cin>>n>>m;
for1(n){
int x,y;cin>>x>>y;
A[i]={x,y};
vec.pb(x);vec.pb(y);
vec.pb(x+y);
}
for1(m){
int a,b,c;cin>>a>>b>>c;
c=max(c,a+b);
B[i]={{a,b},c};
vec.pb(a);vec.pb(b);
vec.pb(c);
}
sort(all(vec));vec.resize(unique(all(vec))-vec.begin());
for1(n)
ad[gt(A[i].F+A[i].S)].pb({gt(A[i].F),gt(A[i].S)});
for1(m)Q[gt(B[i].S)].pb({{gt(B[i].F.F),gt(B[i].F.S)},i});
for(int i=vec.size()-1;i>=1;i--){
for(pii p:ad[i]){upd(p.F,1,0);upd(p.S,1,1);num++;}
for(pair<pii,int>p:Q[i])
ans[p.S]=num-get(p.F.F-1,0)-get(p.F.S-1,1);
}
for1(m)cout<<ans[i]<<endl;
}
# | 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... |