#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int a[MAXN];
int b[MAXN];
int n;
int sol[MAXN];
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> idsz;
vector <int> ids;
int pozicija[MAXN];
int BLOCK;
vector <int> moalgo[400];
bool active[MAXN];
void add(int idx)
{
//idx orig niz
int mopoz = pozicija[idx];
int bl = mopoz/BLOCK;
moalgo[bl].push_back(a[idx]+b[idx]);
sort(moalgo[bl].begin(),moalgo[bl].end());
active[idx]=true;
}
int query(int y,int z)
{
int now = 0;
while(1)
{
if(now >= n)break;
int realid = ids[now];
if(b[realid] >= y)break;
now += BLOCK;
}
if(now >= n)return 0;
int ret = 0;
int blo = now/BLOCK;
if(blo > 0)
{
for(int j = now-BLOCK; j < now; j++)
{
int realid = ids[j];
if(!active[realid])continue;
if(a[realid]+b[realid]>=z)ret++;
}
}
for(;now < n;blo += 1,now+=BLOCK)
{
auto it = lower_bound(moalgo[bl].begin(),moalgo[bl].end(),z);
int pos = it-moalgo[bl].begin();
ret += moalgo[bl].size()-pos;
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
int q;
BLOCK = sqrt(n);
cin >> n >> q;
for(int i = 0; i < n; i++)
{
cin >> a[i] >> b[i];
idsz.push_back(i);
ids.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(idsz.begin(),idsz.end(),cmpp);
sort(ids.begin(),ids.end(),cmppp);
for(int i = 0; i < ids.size(); i++)pozicija[ids[i]]=i;
int now = 0;
for(int i = 0; i < q; i++)
{
while(now < n && a[idsz[now]] >= q[i].x)add(idsz[now]),now++;
sol[qq[i].id]=query(qq[i].y,qq[i].z);
}
for(int i = 0; i < q; i++)cout << sol[i] << "\n";
return 0;
}
Compilation message
examination.cpp: In function 'int query(int, int)':
examination.cpp:72:34: error: 'bl' was not declared in this scope; did you mean 'blo'?
72 | auto it = lower_bound(moalgo[bl].begin(),moalgo[bl].end(),z);
| ^~
| blo
examination.cpp: In function 'int main()':
examination.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < ids.size(); i++)pozicija[ids[i]]=i;
| ~~^~~~~~~~~~~~
examination.cpp:103:41: error: invalid types 'int[int]' for array subscript
103 | while(now < n && a[idsz[now]] >= q[i].x)add(idsz[now]),now++;
| ^
