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...