#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <tuple>
using namespace std;
const int MAXN = 100007, MAXC = 2e9 + 7;
vector<int> val_x, val_y;
pair<int, int> pnts[MAXN];
int N, Q, X[MAXN], Y[MAXN], Z[MAXN], ans[MAXN];
vector<int> queries;
struct IT2D
{
int bit[MAXN];
void init() { memset(bit, 0, sizeof bit); }
void upd(int i, int x) { for (++i; i < MAXN; i += i & (-i)) bit[i] += x; }
int get(int i) { int ans = 0; for (++i; i > 0; i -= i & (-i)) ans += bit[i]; return ans; }
} bit_x, bit_y;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> Q;
for (int i = 0; i < N; ++i) {
cin >> pnts[i].first >> pnts[i].second;
val_x.push_back(pnts[i].first);
val_y.push_back(pnts[i].second);
}
sort(val_x.begin(), val_x.end()); val_x.erase(unique(val_x.begin(), val_x.end()), val_x.end());
sort(val_y.begin(), val_y.end()); val_y.erase(unique(val_y.begin(), val_y.end()), val_y.end());
for (int i = 0; i < Q; ++i) { cin >> X[i] >> Y[i] >> Z[i]; Z[i] = max(Z[i], X[i] + Y[i]); }
queries.resize(Q);
iota(queries.begin(), queries.end(), 0);
// iterate x
sort(pnts, pnts + N, [&](pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; } );
sort(queries.begin(), queries.end(), [&](int i, int j) { return X[i] < X[j]; });
bit_x.init(); bit_y.init();
for (int i = 0, j = 0; i < N || j < Q;) {
if (j < Q && (i == N || X[queries[j]] <= pnts[i].first)) {
ans[queries[j]] += i;
++j;
} else {
bit_y.upd(lower_bound(val_y.begin(), val_y.end(), pnts[i].second) - val_y.begin(), 1);
++i;
}
}
// cerr << "S" << endl;
for (int id = 0; id < Q; ++id) ans[id] += bit_y.get(lower_bound(val_y.begin(), val_y.end(), Y[id]) - val_y.begin() - 1);
// iterate x + y), 0);
sort(pnts, pnts + N, [&](pair<int, int> p1, pair<int, int> p2) { return p1.first + p1.second < p2.first + p2.second; } );
sort(queries.begin(), queries.end(), [&](int i, int j) { return Z[i] < Z[j]; });
bit_x.init(); bit_y.init();
for (int i = 0, j = 0; i < N || j < Q;) {
if (j < Q && (i == N || Z[queries[j]] <= pnts[i].first + pnts[i].second)) {
ans[queries[j]] += i;
ans[queries[j]] -= bit_x.get(lower_bound(val_x.begin(), val_x.end(), X[queries[j]]) - val_x.begin() - 1);
ans[queries[j]] -= bit_y.get(lower_bound(val_y.begin(), val_y.end(), Y[queries[j]]) - val_y.begin() - 1);
++j;
} else {
bit_x.upd(lower_bound(val_x.begin(), val_x.end(), pnts[i].first) - val_x.begin(), 1);
bit_y.upd(lower_bound(val_y.begin(), val_y.end(), pnts[i].second) - val_y.begin(), 1);
++i;
}
}
for (int i = 0; i < Q; ++i) {
cout << N - ans[i] << '\n';
}
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:38:5: error: 'iota' was not declared in this scope
iota(queries.begin(), queries.end(), 0);
^~~~
examination.cpp:38:5: note: suggested alternative: 'int'
iota(queries.begin(), queries.end(), 0);
^~~~
int
