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 <iostream>
#include <algorithm>
#include <vector>
#define fs first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int inf = 1e9;
struct query {
int x, y, z, i;
void scan(int idx) {
i = idx;
cin >> x >> y >> z;
}
bool operator<(const query &p) const {
return z < p.z;
}
} qs[100000];
int ans[100000];
pii ps[100000];
struct fenwick1D {
vector<int> comp, seg;
void add(int x) {
comp.push_back(x);
}
void init() {
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
seg.resize(comp.size(), 0);
}
void update(int i) {
i = lower_bound(comp.begin(), comp.end(), i + 1) - comp.begin();
while (i <= comp.size()) {
++seg[i - 1];
i += i & -i;
}
}
int query(int i) {
i = lower_bound(comp.begin(), comp.end(), i + 1) - comp.begin();
int ret = 0;
while (i) {
ret += seg[i - 1];
i -= i & -i;
}
return ret;
}
};
struct fenwick2D {
vector<int> comp;
vector<fenwick1D> seg;
void add1(int x) {
comp.push_back(x);
}
void init1() {
sort(comp.begin(), comp.end());
comp.erase(unique(comp.begin(), comp.end()), comp.end());
seg.resize(comp.size());
}
void add2(int i, int x) {
i = lower_bound(comp.begin(), comp.end(), i) - comp.begin() + 1;
while (i <= comp.size()) {
seg[i - 1].add(x);
i += i & -i;
}
}
void init2() {
for (auto &i : seg) i.init();
}
void update(int i, int j) {
i = lower_bound(comp.begin(), comp.end(), i + 1) - comp.begin();
while (i <= comp.size()) {
seg[i - 1].update(j);
i += i & -i;
}
}
int query(int i, int j) {
i = lower_bound(comp.begin(), comp.end(), i + 1) - comp.begin();
int ret = 0;
while (i) {
ret += seg[i - 1].query(j);
i -= i & -i;
}
return ret;
}
} seg;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) {
int x, y;
cin >> x >> y;
ps[i] = pii(x, y);
seg.add1(inf - x);
}
seg.init1();
for (int i = 0; i < n; ++i) seg.add2(inf - ps[i].fs, inf - ps[i].se);
seg.init2();
sort(ps, ps + n, [&](pii x, pii y) {
return x.fs + x.se < y.fs + y.se;
});
for (int i = 0; i < q; ++i) qs[i].scan(i);
sort(qs, qs + q);
for (int i = q, j = n - 1; i--; ) {
while (0 <= j && qs[i].z <= ps[j].fs + ps[j].se)
seg.update(inf - ps[j].fs, inf - ps[j].se), --j;
ans[qs[i].i] = seg.query(inf - qs[i].x, inf - qs[i].y);
}
for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message (stderr)
examination.cpp: In member function 'void fenwick1D::update(int)':
examination.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i <= comp.size()) {
~~^~~~~~~~~~~~~~
examination.cpp: In member function 'void fenwick2D::add2(int, int)':
examination.cpp:65:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i <= comp.size()) {
~~^~~~~~~~~~~~~~
examination.cpp: In member function 'void fenwick2D::update(int, int)':
examination.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i <= comp.size()) {
~~^~~~~~~~~~~~~~
# | 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... |