#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
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 = 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 = 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: In instantiation of 'void implicit_segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
examination.cpp:35:3: required from 'void implicit_segment_tree<T>::point_update(int, T) [with T = int]'
examination.cpp:115:33: required from here
examination.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int middle = l + r >> 1;
| ~~^~~
examination.cpp: In instantiation of 'T implicit_segment_tree<T>::query(int, int, int, int, int) [with T = int]':
examination.cpp:65:36: required from 'T implicit_segment_tree<T>::query(int, int) [with T = int]'
examination.cpp:119:52: required from here
examination.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int middle = l + r >> 1;
| ~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
504 ms |
8724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
504 ms |
8724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
