#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Query {
int type, s, t, sum, idx;
};
struct segment_tree {
vector<int> tree;
int n;
void build(int sz) {
tree.resize(4 * sz, 0);
n = sz;
}
void update(int i, int L, int R, int p) {
if (L == R) {
tree[i]++;
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (p <= m) {
update(x, L, m, p);
} else {
update(y, m + 1, R, p);
}
tree[i] = tree[x] + tree[y];
}
void update(int p) {
update(0, 0, n - 1, p);
}
int query(int i, int L, int R, int l, int r) {
if (L == l && r == R) {
return tree[i];
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (r <= m) {
return query(x, L, m, l, r);
} else if (l > m) {
return query(y, m + 1, R, l, r);
} else {
int q1 = query(x, L, m, l, m);
int q2 = query(y, m + 1, R, m + 1, r);
return q1 + q2;
}
}
int query(int l, int r) {
return query(0, 0, n - 1, l, r);
}
} A, B, C;
int main() {
cin.tie(0) -> sync_with_stdio(0);
int n, k;
cin >> n >> k;
vector<Query> a(n + k);
vector<Query> b(n + k);
vector<Query> c(n + k);
for (int i = 0; i < n; ++i) {
int s, t;
cin >> s >> t;
a[i] = {0, s, t, s + t, -1};
b[i] = {0, s, t, s + t, -1};
c[i] = {0, s, t, s + t, -1};
}
for (int i = n; i < n + k; ++i) {
int s, t, sum;
cin >> s >> t >> sum;
a[i] = {1, s, t, sum, i - n};
b[i] = {1, s, t, sum, i - n};
c[i] = {1, s, t, sum, i - n};
}
sort(a.begin(), a.end(), [](const Query &x, const Query &y) {
if (x.s != y.s) return x.s > y.s;
return x.type < y.type;
});
sort(b.begin(), b.end(), [](const Query &x, const Query &y) {
if (x.t != y.t) return x.t > y.t;
return x.type < y.type;
});
sort(c.begin(), c.end(), [](const Query &x, const Query &y) {
if (x.sum != y.sum) return x.sum > y.sum;
return x.type < y.type;
});
int sz = 0;
for (int i = 0; i < n + k; ++i) {
sz = max({sz, a[i].s, b[i].t, c[i].sum});
}
A.build(sz + 1);
B.build(sz + 1);
C.build(sz + 1);
vector<int> ac(k), bc(k), cc(k);
for (Query &q: a) {
if (q.type == 1) {
ac[q.idx] = A.query(q.sum, sz);
} else {
A.update(q.sum);
}
}
for (Query &q: b) {
if (q.type == 1) {
bc[q.idx] = B.query(q.sum, sz);
} else {
B.update(q.sum);
}
}
for (Query &q: c) {
if (q.type == 1) {
cc[q.idx] = C.query(q.sum, sz);
} else {
C.update(q.sum);
}
}
for (int i = 0; i<k; ++i) {
// cout << ac[i] << " + " << bc[i] << " - " << cc[i] << '\n';
cout << ac[i] + bc[i] - cc[i] << '\n';
}
}
# | 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... |