Submission #984935

#	Time	Username	Problem	Language	Result	Execution time	Memory
984935		Pannda	Examination (JOI19_examination)	C++17	41 / 100	688 ms	75312 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 = 100000;
    Fenwick2D fen(C + 1, C + 1);

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

    fen.work();

    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;
        queries[i] = {x, y, z, i};
    }

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

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

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

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