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 maxn = 1e5 + 5;
const int inf = 1e9;
int n, q, s[maxn], t[maxn];
int a[maxn], b[maxn];
int ord[maxn];
vector<int> bit[maxn];
int ans[maxn];
struct query {
int x, y, z, id;
bool operator<(const query &o) {
return z > o.z;
}
} que[maxn];
vector<int> cx, cy;
#define gb(x) (x) & (-x)
struct fenwick_tree {
int n;
vector<int> bit;
fenwick_tree() {}
fenwick_tree(int n) : n(n), bit(n + 5) {}
inline void update(int x, int val) {
for(int i = x; i <= n; i += gb(i)) bit[i] = bit[i] + val;
}
inline int get(int x) {
int ans = 0;
for(int i = x; i > 0; i -= gb(i)) ans = ans + bit[i];
return ans;
}
} tree[maxn];
vector<int> sz[maxn];
struct segment_tree {
int n;
segment_tree() {}
segment_tree(int n) : n(n) {}
inline void resize_tree(int pos, int fen_pos) {
for(int i = pos; i <= n; i += gb(i)) {
sz[i].push_back(fen_pos);
}
}
inline void refine() {
for(int ind = 1; ind <= n; ++ind) {
if(sz[ind].empty()) continue;
sort(sz[ind].begin(), sz[ind].end());
sz[ind].erase(unique(sz[ind].begin(), sz[ind].end()), sz[ind].end());
tree[ind] = fenwick_tree((int)sz[ind].size() + 2);
}
}
inline void update(int pos, int fen_pos, int val) {
int p;
for(int i = pos; i <= n; i += gb(i)) {
p = lower_bound(sz[i].begin(), sz[i].end(), fen_pos) - sz[i].begin() + 1;
tree[i].update(p, val);
}
}
inline int get(int pos, int fen_pos) {
int ans = 0;
int p;
for(int i = pos; i > 0; i -= gb(i)) {
p = upper_bound(sz[i].begin(), sz[i].end(), fen_pos) - sz[i].begin();
if(p == 0) continue;
ans = ans + tree[i].get(p);
}
return ans;
}
int get(int l, int r, int pos) {
return get(r, pos) - get(l - 1, pos);
}
} st;
void solve() {
cin >> n >> q;
for(int i = 1; i <= n; ++i) {
cin >> s[i] >> t[i];
}
for(int i = 1; i <= q; ++i) {
cin >> que[i].x >> que[i].y >> que[i].z;
que[i].id = i;
}
iota(ord + 1, ord + n + 1, 1);
sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
return (s[x] + t[x]) > (s[y] + t[y]);
});
for(int i = 1; i <= n; ++i) {
cx.push_back(s[i]);
cy.push_back(t[i]);
}
sort(cx.begin(), cx.end());
sort(cy.begin(), cy.end());
cx.erase(unique(cx.begin(), cx.end()), cx.end());
cy.erase(unique(cy.begin(), cy.end()), cy.end());
st = segment_tree((int)cx.size());
for(int i = 1; i <= n; ++i) {
a[i] = lower_bound(cx.begin(), cx.end(), s[i]) - cx.begin() + 1;
b[i] = lower_bound(cy.begin(), cy.end(), t[i]) - cy.begin() + 1;
st.resize_tree(a[i], t[i]);
}
st.refine();
sort(que + 1, que + q + 1);
int j = 1;
for(int i = 1; i <= q; ++i) {
while(j <= n and s[ord[j]] + t[ord[j]] >= que[i].z) {
st.update(a[ord[j]], t[ord[j]], 1);
++j;
}
int p = lower_bound(cx.begin(), cx.end(), que[i].x) - cx.begin() + 1;
ans[que[i].id] = st.get(p, (int)cx.size(), inf);
ans[que[i].id] -= st.get(p, (int)cx.size(), que[i].y - 1);
}
for(int i = 1; i <= q; ++i) {
cout << ans[i] << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# | 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... |