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>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 100010;
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
struct SegTree {
vector<int> st[MAXN << 2], t[MAXN << 2];
void build(int id, int l, int r, vector<int> &vs, vector<vector<int>> &vt) {
For(it, l, r) for(auto &j:vt[it]) {
t[id].eb(j);
st[id].eb(vs[it] + j);
}
sort(all(t[id]));
sort(all(st[id]));
if(l == r) return;
int m = (l + r) / 2;
build(L(id), l, m, vs, vt);
build(R(id), m + 1, r, vs, vt);
}
int count(const vector<int> &v, int x) {
return v.end() - lower_bound(all(v), x);
}
int ask(int id, int l, int r, int L, int R, int type, int x) {
if(l >= L && r <= R) {
if(type) return count(t[id], x);
return count(st[id], x);
}
int m = (l + r) / 2;
if(R <= m) return ask(L(id), l, m, L, R, type, x);
if(L > m) return ask(R(id), m + 1, r, L, R, type, x);
return ask(L(id), l, m, L, R, type, x) +
ask(R(id), m + 1, r, L, R, type, x);
}
} seg;
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
// nyanyanyanyanya
int n, q; cin >> n >> q;
vector<pii> pts;
vector<int> vs;
For(i, 1, n) {
int s, t; cin >> s >> t;
pts.eb(s, t);
vs.eb(s);
}
sort(all(vs));
vs.erase(unique(all(vs)), vs.end());
int m = sz(vs);
vector<vector<int>> vt(m);
for(auto &p:pts) {
int it = lower_bound(all(vs), p.F) - vs.begin();
vt[it].eb(p.S);
}
seg.build(0, 0, m - 1, vs, vt);
while(q--) {
int a, b, c; cin >> a >> b >> c;
int res;
if(a + b >= c) {
int p = lower_bound(all(vs), a) - vs.begin();
res = seg.ask(0, 0, m - 1, p, m, 1, b);
} else {
int p1 = lower_bound(all(vs), a) - vs.begin();
int p2 = lower_bound(all(vs), c - b) - vs.begin();
res = seg.ask(0, 0, m - 1, p1, p2 - 1, 0, c) +
seg.ask(0, 0, m - 1, p2, m, 1, b);
}
cout << res << "\n";
}
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... |