Submission #549419

#	Time	Username	Problem	Language	Result	Execution time	Memory
549419		jesus_coconut	Examination (JOI19_examination)	C++17	100 / 100	153 ms	12404 KiB

examination

#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 ll = long long;
using pii = pair<ll, ll>;

int const N = 300005;

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() {
    xs.reserve(n);
    ys.reserve(n);
    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]) {
            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);
    cerr << INT_MAX << endl;
    load();
    solve();


    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57