#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int a[MAXN];
int b[MAXN];
int sol[MAXN];
int n;
int BLOCK;
vector <int> ids;
vector <int> idsz;
struct que
{
int x,y,z;
int id;
};
que qq[MAXN];
bool cmp(que a,que b)
{
return a.x > b.x;
}
bool cmpp(int x,int y)
{
return a[x]>a[y];
}
bool cmppp(int x,int y)
{
return b[x]<b[y];
}
vector <int> strk[400];
int pozniz[MAXN];
bool active[MAXN];
void update(int origid)
{
int pozuniz = pozniz[origid];
int bl = pozuniz/BLOCK;
strk[bl].push_back(a[origid]+b[origid]);
sort(strk[bl].begin(),strk[bl].end());
active[origid]=true;
}
int lowb(int y)
{
int lo = 0,hi=n-1,r=n;
int mid;
while(lo <= hi)
{
mid=lo+hi>>1;
if(b[idsz[mid]]>=y)r=mid,hi=mid-1;
else lo=mid+1;
}
return r;
}
int query(int y,int z)
{
int ans = 0;
int bl = 0;
int startpos = lowb(y);
while(startpos%BLOCK != 0 && startpos < n)
{
if(!active[idsz[startpos]]){startpos++;continue;}
if(a[idsz[startpos]]+b[idsz[startpos]] >= z)ans++;
startpos++;
}
if(startpos % BLOCK != 0 || startpos == n)return ans;
for(int bl = startpos/BLOCK; bl <= (n-1)/BLOCK; bl++)
{
auto it = lower_bound(strk[bl].begin(),strk[bl].end(),z);
int pos = it-strk[bl].begin();
ans += max(0,n-1-pos+1);
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
int q;
cin >> n >> q;
BLOCK = sqrt(n);
for(int i = 0; i < n; i++)
{
cin >> a[i] >> b[i];
ids.push_back(i);
idsz.push_back(i);
}
for(int i = 0; i < q; i++)
{
cin >> qq[i].x >> qq[i].y >> qq[i].z;
qq[i].id=i;
}
sort(qq,qq+q,cmp);
sort(ids.begin(),ids.end(),cmpp);
sort(idsz.begin(),idsz.end(),cmppp);
for(int i = 0; i < idsz.size(); i++)pozniz[idsz[i]]=i;
int now = 0;
for(int i = 0; i < q; i++)
{
while(q[i].x <= a[ids[now]] && now < n)update(now),now++;
ans[q[i].id]=query(q[i].y,q[i].z);
}
for(int i = 0; i < q; i++)cout << ans[i] << "\n";
return 0;
}
/*
5 4
35 100
70 70
45 15
80 40
20 95
20 50 120
10 10 100
60 60 80
0 100 100
*/
Compilation message
examination.cpp: In function 'int lowb(int)':
examination.cpp:52:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | mid=lo+hi>>1;
| ~~^~~
examination.cpp: In function 'int query(int, int)':
examination.cpp:62:7: warning: unused variable 'bl' [-Wunused-variable]
62 | int bl = 0;
| ^~
examination.cpp: In function 'int main()':
examination.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0; i < idsz.size(); i++)pozniz[idsz[i]]=i;
| ~~^~~~~~~~~~~~~
examination.cpp:104:14: error: invalid types 'int[int]' for array subscript
104 | while(q[i].x <= a[ids[now]] && now < n)update(now),now++;
| ^
examination.cpp:105:5: error: 'ans' was not declared in this scope; did you mean 'abs'?
105 | ans[q[i].id]=query(q[i].y,q[i].z);
| ^~~
| abs
examination.cpp:105:12: error: invalid types 'int[int]' for array subscript
105 | ans[q[i].id]=query(q[i].y,q[i].z);
| ^
examination.cpp:105:27: error: invalid types 'int[int]' for array subscript
105 | ans[q[i].id]=query(q[i].y,q[i].z);
| ^
examination.cpp:105:34: error: invalid types 'int[int]' for array subscript
105 | ans[q[i].id]=query(q[i].y,q[i].z);
| ^
examination.cpp:107:37: error: 'ans' was not declared in this scope; did you mean 'abs'?
107 | for(int i = 0; i < q; i++)cout << ans[i] << "\n";
| ^~~
| abs
