Submission #113254

#TimeUsernameProblemLanguageResultExecution timeMemory
113254imeimi2000Examination (JOI19_examination)C++17
100 / 100
585 ms25652 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...