#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
struct Query {
int type, s, t, sum, idx;
};
vector<Query> queries;
vector<vector<ll>> st;
void update(int i, int L, int R, int p, int v) {
if (L == R) {
st[i].push_back(v);
return;
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (p <= m) {
update(x, L, m, p, v);
} else {
update(y, m + 1, R, p, v);
}
st[i].clear();
merge(st[x].begin(), st[x].end(), st[y].begin(), st[y].end(), back_inserter(st[i]));
}
int query(int i, int L, int R, int l, int r, int v) {
if (L == l && r == R) {
auto it = lower_bound(st[i].begin(), st[i].end(), v);
return int(st[i].end() - it);
}
int m = (L + R) / 2;
int x = 2 * i + 1, y = x + 1;
if (r <= m) {
return query(x, L, m, l, r, v);
} else if (l > m) {
return query(y, m + 1, R, l, r, v);
} else {
int q1 = query(x, L, m, l, m, v);
int q2 = query(y, m + 1, R, m + 1, r, v);
return q1 + q2;
}
}
signed main() {
int n, k;
cin >> n >> k;
queries.resize(n + k);
for (int i = 0; i < n; ++i) {
cin >> queries[i].s >> queries[i].t;
queries[i].type = 0;
queries[i].sum = queries[i].s + queries[i].t;
queries[i].idx = -1;
}
for (int i = n; i < n + k; ++i) {
cin >> queries[i].s >> queries[i].t >> queries[i].sum;
queries[i].idx = i - n;
queries[i].type = 1;
}
sort(queries.begin(), queries.end(), [](const Query &a, const Query &b) {
if (a.s != b.s) return a.s > b.s;
if (a.t != b.t) return a.t > b.t;
return a.sum > b.sum;
});
int sz = 0;
for (Query &q : queries) {
// cout << q.type << ' ' << q.s << ' ' << q.t << ' ' << q.sum << '\n';
sz = max(sz, q.t);
}
st.resize(4 * sz + 5);
vector<int> res(k);
for (Query &q : queries) {
int type = q.type;
if (type == 0) {
update(0, 0, sz, q.t, q.sum);
} else {
int cnt = query(0, 0, sz, q.t, sz, q.sum);
if (q.idx >= 0)
res[q.idx] = cnt;
}
}
for (int &i : res) {
cout << 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... |