제출 #549411

#제출 시각아이디문제언어결과실행 시간메모리
549411jesus_coconutExamination (JOI19_examination)C++17
43 / 100
160 ms10248 KiB
#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)
#define pb push_back
using namespace std;

using pii = pair<int, int>;

int const N = 100005;

int n, q;
vector<pii> v;
vector<array<int, 4>> qs;

void load() {
    cin >> n >> q;
    v.resize(n);
    qs.resize(q);
    for (auto &[a, b] : v) cin >> a >> b;
    for (int i = 0; i < q; ++i) {
        cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
        qs[i][2] = max(qs[i][2], qs[i][0] + qs[i][1]);
        qs[i][3] = i;
    }
}

struct BIT {
    array<int, N> bit;

    void add(int p, int k) {
        for (++p; p < N; p += p & -p) {
            bit[p] += k;
        }
    }

    int sum(int r) {
        int val = 0;
        for (; r > 0; r -= r & -r) {
            val += bit[r];
        }
        return val;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l);
    }
};

vector<int> xs, ys;

void compress() {
    for (auto [a, b] : v) {
        xs.pb(a);
        ys.pb(b);
    }
    sort(all(xs));
    sort(all(ys));
    xs.erase(unique(all(xs)), end(xs));
    ys.erase(unique(all(ys)), end(ys));
}

void solve() {
    sort(all(qs), [](auto const &a, auto const &b) {
        return a[2] > b[2];
    });
    sort(all(v), [](auto const &a, auto const &b) {
        return a.F + a.S > b.F + b.S;
    });
    compress();
    int sz = 0;
    vector<int> ans(q);
    BIT valx, valy;
    for (auto arr : qs) {
        while (sz < n && v[sz].F + v[sz].S >= arr[2]) {
         //   cerr << v[sz].F << ' ' << v[sz].S << endl;
            valx.add(lower_bound(all(xs), v[sz].F) - begin(xs), 1);
            valy.add(lower_bound(all(ys), v[sz].S) - begin(ys), 1);
            sz++;
        }
        ans[arr[3]] = sz - valx.sum(lower_bound(all(xs), arr[0]) - begin(xs)) - valy.sum(lower_bound(all(ys), arr[1]) - begin(ys));
    }
    for (auto a : ans) cout << a << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    load();
    solve();


    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...