This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
template <typename T>
struct fenwick_tree {
int size;
vector<T> tree;
T neutral;
fenwick_tree(int n, T _neutral) {
size = n;
neutral = _neutral;
tree = vector<T>(n + 1);
}
void update(int index, T value) {
for(; index <= size; index += index & -index) {
tree[index] += value;
}
}
T query_prefix(int index) {
T ans = neutral;
for(; index; index -= index & -index) {
ans += tree[index];
}
return ans;
}
T query(int l, int r) {
return query_prefix(r) - query_prefix(l - 1);
}
};
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;
}
struct point {
int x, y, sum;
bool operator < (const point &other) {
if(x == other.x) {
return y < other.y;
}
return x < other.x;
}
};
point a[N], b[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 >> a[i].x >> a[i].y;
a[i].sum = a[i].x + a[i].y;
sorted_sums.push_back(a[i].sum);
}
sort(sorted_sums.begin(), sorted_sums.end());
sort(a + 1, a + n + 1);
for(int i = 1; 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);
}
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] = b[i].sum;
}
for(int i = 1; i <= n; ++i) {
coords[i + m - 1] = a[i].sum;
}
compressed_sum = compress(coords);
//x
for(int i = 1; i <= m; ++i) {
coords[i - 1] = b[i].x;
}
for(int i = 1; i <= n; ++i) {
coords[i + m - 1] = a[i].x;
}
compressed_x = compress(coords);
//y
for(int i = 1; i <= m; ++i) {
coords[i - 1] = b[i].y;
}
for(int i = 1; i <= n; ++i) {
coords[i + m - 1] = a[i].y;
}
compressed_y = compress(coords);
auto sum = [](int x, int y) -> int {
return x + y;
};
fenwick_tree<int> tx(N, 0);
fenwick_tree<int> ty(N, 0);
vector<int> ans(m+1);
for(int i = 1; i <= m; ++i) {
int l = 0, r = n - 1, ind = n;
while(r >= l) {
int middle = l + r >> 1;
if(sorted_sums[middle] >= b[i].sum) {
r = middle - 1;
ind = middle;
} else {
l = middle + 1;
}
}
ans[i] = n - ind;
}
for(int i = 1; i <= n; ++i) {
a[i].x = compressed_x[a[i].x];
a[i].y = compressed_y[a[i].y];
a[i].sum = compressed_sum[a[i].sum];
}
for(int i = 1; i <= m; ++i) {
b[i].x = compressed_x[b[i].x];
b[i].y = compressed_y[b[i].y];
b[i].sum = compressed_sum[b[i].sum];
}
vector<int> sums[N], queries[N];
for(int i = 1; i <= n; ++i) {
int val = a[i].sum;
sums[val].push_back(i);
}
for(int i = 1; i <= m; ++i) {
int val = b[i].sum;
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 = a[id].x;
int val_y = a[id].y;
tx.update(val_x, 1);
ty.update(val_y, 1);
}
for(int id : queries[i]) {
int val_x = b[id].x;
int val_y = b[id].y;
ans[id] -= tx.query_prefix(val_x - 1);
ans[id] -= ty.query_prefix(val_y - 1);
}
}
for(int i = 1; i <= m; ++i) {
cout << ans[i] << '\n';
}
}
Compilation message (stderr)
examination.cpp: In function 'int main()':
examination.cpp:102:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | int middle = l + r >> 1;
| ~~^~~
examination.cpp:93:7: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
93 | auto sum = [](int x, int y) -> int {
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |