Submission #984954

#	Time	Username	Problem	Language	Result	Execution time	Memory
984954		Pannda	Examination (JOI19_examination)	C++17	100 / 100	833 ms	78248 KiB

examination

#include <bits/stdc++.h>
using namespace std;

struct Fenwick2D {
    int n, m;
    vector<vector<int>> bit;
    vector<vector<int>> f;

    Fenwick2D(int n, int m) : n(n), m(m), bit(n + 1), f(n + 1) {}

    void fakeAdd(int i0, int j0) {
        for (int i = i0 + 1; i <= n; i += i & -i) {
            for (int j = j0 + 1; j <= m; j += j & -j) {
                f[i].push_back(j);
            }
        }
    }

    void work() {
        for (int i = 1; i <= n; i++) {
            f[i].push_back(0);
            sort(f[i].begin(), f[i].end());
            f[i].resize(unique(f[i].begin(), f[i].end()) - f[i].begin());
            bit[i].resize(f[i].size(), 0);
        }
    }

    void add(int i0, int j0, int x) {
        for (int i = i0 + 1; i <= n; i += i & -i) {
            for (int j = lower_bound(f[i].begin(), f[i].end(), j0 + 1) - f[i].begin(); j < (int)f[i].size(); j += j & -j) {
                bit[i][j] += x;
            }
        }
    }

    int sum(int i0, int j0) {
        int res = 0;
        for (int i = i0; i > 0; i -= i & -i) {
            for (int j = upper_bound(f[i].begin(), f[i].end(), j0) - f[i].begin() - 1; j > 0; j -= j & -j) {
                res += bit[i][j];
            }
        }
        return res;
    }
};

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

    constexpr int C = 1e9;

    int n, q;
    cin >> n >> q;
    vector<array<int, 2>> a(n);
    vector<int> xs, ys;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x = C - x;
        y = C - y;
        a[i] = {x, y};
        xs.push_back(x);
        ys.push_back(y);
    }

    sort(a.begin(), a.end(), [&](array<int, 2> x, array<int, 2> y) { return x[0] + x[1] < y[0] + y[1]; });

    vector<array<int, 4>> queries(q);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x = C - x + 1;
        y = C - y + 1;
        queries[i] = {x, y, z, i};
    }

    sort(queries.begin(), queries.end(), [&](array<int, 4> x, array<int, 4> y) { return x[2] > y[2]; });

    sort(xs.begin(), xs.end());
    sort(ys.begin(), ys.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    int X = xs.size();
    int Y = ys.size();

    Fenwick2D fen(X, Y);
    for (auto &[x, y] : a) {
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        y = lower_bound(ys.begin(), ys.end(), y) - ys.begin();
        fen.fakeAdd(x, y);
    }
    fen.work();

    int ptr = 0;
    for (auto [x, y, z, id] : queries) {
        while (ptr < n && C + C - xs[a[ptr][0]] - ys[a[ptr][1]] >= z) {
            auto [x, y] = a[ptr];
            fen.add(x, y, +1);
            ptr++;
        }
        x = lower_bound(xs.begin(), xs.end(), x) - xs.begin();
        y = lower_bound(ys.begin(), ys.end(), y) - ys.begin();
        ans[id] = fen.sum(x, y);
    }

    for (int x : ans) {
        cout << x << '\n';
    }
}

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