#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
//~ #define int long long
typedef long long int ll;
const int MOD = 1e9 + 7;
const int maxN = 200000;
bool cmp(pair<int, int> a, pair<int, int> b){
return a.first + a.second > b.first + b.second;
}
bool cmp2(tuple<int, int, int, int> a, tuple<int, int, int, int> b){
return get<2>(a) > get<2>(b);
}
struct segTree {
vector<ll> bit;
init(int n) {
bit.assign(n+1, 0);
}
ll sum(int r) {
ll sum = 0;
for (; r > 0; r -= r&-r)
sum += bit[r];
return sum;
}
ll sum(int l, int r) {
return sum(r) - sum(l-1);
}
void add(int r, ll delta) {
for (; r < bit.size(); r += r&-r)
bit[r] += delta;
}
void set(int r, ll x) {
add(r+1, x);
}
};
void solve(){
int n, q; cin >> n >> q;
vector<pair<int, int>> v(n);
set<int> sa;
set<int> sb;
for(int i = 0; i < n; i++){
int x, y; cin >> x >> y;
v[i] = {x, y};
sa.insert(x);
sb.insert(y);
}
map<int, int> a;
map<int, int> b;
int curr = 1;
for(auto x : sa){
a[x] = curr;
curr++;
}
segTree sta; sta.init(curr);
int sza = curr;
curr = 1;
for(auto x : sb){
b[x] = curr;
curr++;
}
segTree stb; stb.init(curr);
int szb = curr;
sort(v.begin(), v.end(), cmp);
vector<tuple<int, int, int, int>> queries(q);
for(int i = 0; i < q; i++){
int x, y, z; cin >> x >> y >> z;
int nx = sza;
auto it = a.lower_bound(x);
if(it != a.end()) nx = (*it).second;
int ny = szb;
it = b.lower_bound(y);
if(it != b.end()) ny = (*it).second;
queries[i] = {nx, ny, max(z, x + y), i};
}
sort(queries.begin(), queries.end(), cmp2);
vector<int> ans(q);
curr = 0;
for(int i = 0; i < q; i++){
while(curr < n && v[curr].first + v[curr].second >= get<2>(queries[i])){
sta.set(a[v[curr].first], 1);
stb.set(b[v[curr].second], 1);
curr++;
}
int total = curr - sta.sum(1, get<0>(queries[i])) - stb.sum(1, get<1>(queries[i]));
ans[get<3>(queries[i])] = total;
}
for(int x : ans) cout << x << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("inpt.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//~ int tt; cin >> tt;
int tt = 1;
for(int t = 1; t <= tt; t++){
solve();
}
}
Compilation message
examination.cpp:26:5: error: ISO C++ forbids declaration of 'init' with no type [-fpermissive]
26 | init(int n) {
| ^~~~
examination.cpp: In member function 'int segTree::init(int)':
examination.cpp:28:5: warning: no return statement in function returning non-void [-Wreturn-type]
28 | }
| ^
examination.cpp: In member function 'void segTree::add(int, ll)':
examination.cpp:42:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (; r < bit.size(); r += r&-r)
| ~~^~~~~~~~~~~~
