#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
template <typename T>
template <typename T>
struct implicit_segment_tree {
T neutral;
int size, max_size;
function<T(T, T)> join;
vector<T> values;
vector<int> left, right;
implicit_segment_tree(int _max_size, T _neutral, function<T(T, T)> f, int reserve_size = 1) {
join = f;
neutral = _neutral;
size = 0;
max_size = _max_size;
values.reserve(reserve_size);
left.reserve(reserve_size);
right.reserve(reserve_size);
insert_node(neutral);
}
T get_val(int pos) {
if(pos < 0 || pos >= (int)values.size()) return neutral;
return values[pos];
}
void insert_node(T val) {
values.push_back(val);
left.push_back(-1);
right.push_back(-1);
++size;
}
void point_update(int id, T val) {
point_update(1, max_size, id, val, 0);
}
void point_update(int l, int r, int x, T val, int p) {
int middle = 0LL + l + r >> 1;
if(l == r) {
values[p] = val;
return;
}
if(x <= middle) {
if(left[p] == -1) {
left[p] = size;
insert_node(neutral);
}
point_update(l, middle, x, val, left[p]);
} else {
if(right[p] == -1) {
right[p] = size;
insert_node(neutral);
}
point_update(middle+1, r, x, val, right[p]);
}
values[p] = join(get_val(left[p]), get_val(right[p]));
}
T get(int id) {
return query(id, id);
}
T query(int L, int R) {
return query(1, max_size, L, R, 0);
}
T query(int l, int r, int L, int R, int p) {
if(L > r || l > R || p == -1) return neutral;
if(L <= l && R >= r) return get_val(p);
int middle = 0LL + l + r >> 1;
T lft = query(l, middle, L, R, left[p]);
T rgh = query(middle+1, r, L, R, right[p]);
return join(lft, rgh);
}
void print_tree(int n) {
for(int i = 1; i <= n; ++i) {
cout << get(i) << " \n"[i == n];
}
}
};
struct point {
int x, y, sum, id;
bool operator < (const point &other) {
return sum < other.sum;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector<point> a(n), b(m);
for(int i = 0; i < n; ++i) {
cin >> a[i].x >> a[i].y;
a[i].sum = a[i].x + a[i].y;
}
for(int i = 0; i < m; ++i) {
cin >> b[i].x >> b[i].y >> b[i].sum;
b[i].sum = max(b[i].sum, b[i].x + b[i].y);
b[i].id = i;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<int> ans(m);
auto sum = [](int x, int y) -> int {
return x + y;
};
implicit_segment_tree<int> tx(INT_MAX, 0, sum);
implicit_segment_tree<int> ty(INT_MAX, 0, sum);
for(int i = m - 1, j = n - 1; i >= 0; --i) {
while(j >= 0 && a[j].sum >= b[i].sum) {
int upd_x = tx.get(a[j].x) + 1;
int upd_y = ty.get(a[j].y) + 1;
tx.point_update(a[j].x, upd_x);
ty.point_update(a[j].y, upd_y);
--j;
}
ans[b[i].id] = n - j - 1 - tx.query(1, b[i].x - 1) - ty.query(1, b[i].y - 1);
}
for(int x : ans) {
cout << x << ' ';
}
}
Compilation message
examination.cpp:5:11: error: declaration of template parameter 'T' shadows template parameter
5 | template <typename T>
| ^~~~~~~~
examination.cpp:4:11: note: template parameter 'T' declared here
4 | template <typename T>
| ^~~~~~~~
examination.cpp:6:8: error: too many template-parameter-lists
6 | struct implicit_segment_tree {
| ^~~~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:110:2: error: 'implicit_segment_tree' was not declared in this scope
110 | implicit_segment_tree<int> tx(INT_MAX, 0, sum);
| ^~~~~~~~~~~~~~~~~~~~~
examination.cpp:110:24: error: expected primary-expression before 'int'
110 | implicit_segment_tree<int> tx(INT_MAX, 0, sum);
| ^~~
examination.cpp:111:24: error: expected primary-expression before 'int'
111 | implicit_segment_tree<int> ty(INT_MAX, 0, sum);
| ^~~
examination.cpp:114:16: error: 'tx' was not declared in this scope; did you mean 'tm'?
114 | int upd_x = tx.get(a[j].x) + 1;
| ^~
| tm
examination.cpp:115:16: error: 'ty' was not declared in this scope; did you mean 'tm'?
115 | int upd_y = ty.get(a[j].y) + 1;
| ^~
| tm
examination.cpp:120:30: error: 'tx' was not declared in this scope; did you mean 'tm'?
120 | ans[b[i].id] = n - j - 1 - tx.query(1, b[i].x - 1) - ty.query(1, b[i].y - 1);
| ^~
| tm
examination.cpp:120:56: error: 'ty' was not declared in this scope; did you mean 'tm'?
120 | ans[b[i].id] = n - j - 1 - tx.query(1, b[i].x - 1) - ty.query(1, b[i].y - 1);
| ^~
| tm
