#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
class BIT2Dx {
public:
const int INF = 2e9;
int n;
vector<vector<int>> nodes, f;
void fakeUpdate(int u, int v){
for (int x = u; x > 0; x -= x & -x)
nodes[x].push_back(v);
}
void fakeGet(int u, int v){
for (int x = u; x <= n; x += x & -x)
nodes[x].push_back(v);
}
void update(int u, int v){
for (int x = u; x > 0; x -= x & -x)
for (int y = upper_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin(); y > 0; y -= y & -y)
f[x][y]++;
}
int get(int u, int v){
int res = 0;
for (int x = u; x <= n; x += x & -x)
for (int y = lower_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin() + 1; y <= nodes[x].size(); y += y & -y)
res += f[x][y];
return res;
}
void init(int _n){
n = _n;
node.assign(n + 5, {});
f.assign(n + 5, {});
}
void normalize(void){
for (int i = 1; i <= n; ++i){
nodes[i].push_back(INF);
sort(nodes[i].begin(), nodes[i].end());
f[i].resize(nodes[i].size() + 3);
}
}
}ft;
int N, Q;
pair<int, int> stu[maxn];
int ans[maxn];
vector<int> val;
int compress(int x)
{
return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}
class Query
{
public:
int A, B, C, id;
}query[maxn];
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("A.INP", "r")){
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
}
cin >> N >> Q;
for (int i = 1; i <= N; ++i){
cin >> stu[i].fi >> stu[i].se;
val.pb(stu[i].fi); val.pb(stu[i].se); val.pb(stu[i].fi + stu[i].se);
}
for (int i = 1; i <= Q; ++i){
query[i].id = i;
cin >> query[i].A >> query[i].B >> query[i].C;
val.pb(query[i].A); val.pb(query[i].B); val.pb(query[i].C);
}
sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end());
ft.init(val.size());
sort(stu + 1, stu + 1 + N, greater<pair<int, int>>());
sort(query + 1, query + 1 + N, [&](const Query & x, const Query & y){
return x.A > y.A;
});
int j = 1;
for (int i = 1; i <= Q; ++i){
while (j <= N && stu[j].fi >= query[i].A){
ft.fakeUpdate(compress(stu[j].se), compress(stu[j].fi + stu[j].se));
++j;
}
ft.fakeGet(compress(query[i].B), compress(query[i].C));
}
ft.normalize();
j = 1;
for (int i = 1; i <= Q; ++i){
while (j <= N && stu[j].fi >= query[i].A){
ft.update(compress(stu[j].se), compress(stu[j].fi + stu[j].se));
++j;
}
ans[query[i].id] = ft.get(compress(query[i].B), compress(query[i].C));
//cerr << ft.get(compress(query[i].B), compress(query[i].C));
}
for (int i = 1; i <= Q; ++i){
cout << ans[i] << '\n';
}
}
Compilation message
examination.cpp: In member function 'int BIT2Dx::get(int, int)':
examination.cpp:38:95: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int y = lower_bound(nodes[x].begin(), nodes[x].end(), v) - nodes[x].begin() + 1; y <= nodes[x].size(); y += y & -y)
~~^~~~~~~~~~~~~~~~~~
examination.cpp: In member function 'void BIT2Dx::init(int)':
examination.cpp:44:7: error: 'node' was not declared in this scope
node.assign(n + 5, {});
^~~~
examination.cpp:44:7: note: suggested alternative: 'nodes'
node.assign(n + 5, {});
^~~~
nodes
examination.cpp: In function 'int main()':
examination.cpp:76:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.INP", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.OUT", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
