#include <bits/stdc++.h>
using namespace std;
const int N = 3e2+10;
template <typename T>
struct segment_tree {
vector<T> tree;
T neutral;
int size;
function<T(T, T)> join;
segment_tree(int _size, T _neutral, function<T(T, T)> f) {
join = f;
size = _size;
tree = vector<T>(4 * size);
neutral = _neutral;
}
void point_update(int id, T val) {
point_update(1, size, id, val, 1);
}
void point_update(int l, int r, int x, T val, int p) {
if(l > x || r < x) {
return;
}
if(l == r) {
tree[p] = val;
return;
}
int middle = l + r >> 1;
point_update(l, middle, x, val, p << 1);
point_update(middle+1, r, x, val, p << 1 | 1);
tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
}
T get(int id) {
return query(id, id);
}
T query(int L, int R) {
return query(1, size, L, R, 1);
}
T query(int l, int r, int L, int R, int p) {
if(L > r || l > R) return neutral;
if(L <= l && R >= r) return tree[p];
int middle = l + r >> 1;
T lft = query(l, middle, L, R, p << 1);
T rgh = query(middle+1, r, L, R, p << 1 | 1);
return join(lft, rgh);
}
};
map<int, int> compress(vector<int> &coords) {
sort(coords.begin(), coords.end());
map<int, int> compressed;
for(int i = 0, current = 0; i < (int)coords.size(); ++i) {
if(i == 0 || coords[i] != coords[i - 1]) ++current;
compressed[coords[i]] = current;
}
return compressed;
}
int x[N], y[N], a[N], b[N], c[N];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> v;
vector<int> sorted_sums;
for(int i = 1; i <= n; ++i) {
cin >> x[i] >> y[i];
sorted_sums.push_back(x[i] + y[i]);
v.push_back({x[i], y[i]});
}
sort(sorted_sums.begin(), sorted_sums.end());
sort(v.begin(), v.end());
for(int i = 1; i <= n; ++i) {
x[i] = v[i - 1][0];
y[i] = v[i - 1][1];
}
v.clear();
for(int i = 1; i <= m; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
vector<int> type1, type2;
for(int i = 1; i <= m; ++i) {
if(a[i] + b[i] >= c[i]) {
type1.push_back(i);
} else {
type2.push_back(i);
}
}
map<int, int> compressed_sum, compressed_x, compressed_y;
//sum
vector<int> coords(n + m);
for(int i = 1; i <= m; ++i) {
coords[i - 1] = c[i];
}
for(int i = 1; i <= n; ++i) {
coords[i + m - 1] = x[i] + y[i];
}
compressed_sum = compress(coords);
//x
for(int i = 1; i <= m; ++i) {
coords[i - 1] = a[i];
}
for(int i = 1; i <= n; ++i) {
coords[i + m - 1] = x[i];
}
compressed_x = compress(coords);
//y
for(int i = 1; i <= m; ++i) {
coords[i - 1] = b[i];
}
for(int i = 1; i <= n; ++i) {
coords[i + m - 1] = y[i];
}
compressed_y = compress(coords);
sort(type1.begin(), type1.end(), [&](int x, int y) {
if(a[x] == a[y]) {
if(b[x] == b[y]) {
return c[x] < c[y];
}
return b[x] < b[y];
}
return a[x] < a[y];
});
auto sum = [](int x, int y) -> int {
return x + y;
};
segment_tree<int> t(N, 0, sum);
segment_tree<int> tx(N, 0, sum);
segment_tree<int> ty(N, 0, sum);
vector<int> ans(m+1);
for(int i = (int)type1.size() - 1, j = n; i >= 0; --i) {
int q_id = type1[i];
while(j > 0 && x[j] >= a[q_id]) {
int val = compressed_y[y[j]];
t.point_update(val, t.get(val)+1);
--j;
}
int val = compressed_y[b[q_id]];
ans[q_id] = t.query(val, t.size);
}
for(int i : type2) {
int l = 0, r = n - 1, ind = n;
while(r >= l) {
int middle = l + r >> 1;
if(sorted_sums[middle] >= c[i]) {
r = middle - 1;
ind = middle;
} else {
l = middle + 1;
}
}
// all[i] = n - ind;
ans[i] = n - ind;
}
vector<int> sums[N], queries[N];
for(int i = 1; i <= n; ++i) {
int val = compressed_sum[x[i] + y[i]];
sums[val].push_back(i);
}
for(int i : type2) {
if(i == -1) continue;
int val = compressed_sum[c[i]];
queries[val].push_back(i);
}
int max_sum_val = (int)compressed_sum.size();
for(int i = max_sum_val; i >= 1; --i) {
for(int id : sums[i]) {
int val_x = compressed_x[x[id]];
int val_y = compressed_y[y[id]];
tx.point_update(val_x, tx.get(val_x)+1);
ty.point_update(val_y, ty.get(val_y)+1);
}
for(int id : queries[i]) {
int val_x = compressed_x[a[id]];
int val_y = compressed_y[b[id]];
/* sumA[id] */ ans[id] -= tx.query(1, val_x - 1);
/* sumB[id] */ ans[id] -= ty.query(1, val_y - 1);
}
}
for(int i = 1; i <= m; ++i) {
cout << ans[i] << '\n';
}
// for (int i = 1; i <= m; ++i) {
// if (a[i] + b[i] >= c[i]) {
// int ans = 0;
// for(int j = 1; j <= n; ++j) {
// if (x[j] >= a[i] && y[j] >= b[i]) {
// ++ans;
// }
// }
// cout << ans << '\n';
// continue;
// }
// int all = 0, sumA = 0, sumB = 0;
// for (int j = 1; j <= n; ++j) {
// if (x[j] + y[j] >= c[i]) {
// ++all;
// }
// if (x[j] < a[i] && x[j] + y[j] >= c[i]) {
// ++sumA;
// }
// if (y[j] < b[i] && x[j] + y[j] >= c[i]) {
// ++sumB;
// }
// }
// cout << all - sumA - sumB << '\n';
// }
}
Compilation message
examination.cpp: In function 'int main()':
examination.cpp:146:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
146 | int middle = l + r >> 1;
| ~~^~~
examination.cpp: In instantiation of 'void segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
examination.cpp:18:3: required from 'void segment_tree<T>::point_update(int, T) [with T = int]'
examination.cpp:137:36: required from here
examination.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int middle = l + r >> 1;
| ~~^~~
examination.cpp: In instantiation of 'T segment_tree<T>::query(int, int, int, int, int) [with T = int]':
examination.cpp:40:32: required from 'T segment_tree<T>::query(int, int) [with T = int]'
examination.cpp:141:34: required from here
examination.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int middle = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
