제출 #1332289

#제출 시각아이디문제언어결과실행 시간메모리
1332289MisterReaperExamination (JOI19_examination)C++20
100 / 100
261 ms11660 KiB
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

struct fenwick {
    int n;
    std::vector<int> tree;
    fenwick(int n_) : n(n_), tree(n + 1) {}
    void modify(int p, int x) {
        for (p += 1; p <= n; p += p & -p) {
            tree[p] += x;
        }
    }
    int get(int p) {
        int res = 0;
        for (p += 1; p; p -= p & -p) {
            res += tree[p];
        }
        return res;
    }
    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

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

    int N, Q;
    std::cin >> N >> Q;

    std::vector<std::array<int, 4>> vv;
    std::vector<int> va, vb, vc;

    for (int i = 0; i < N; ++i) {
        int A, B, C;
        std::cin >> A >> B;
        C = A + B;
        vv.push_back({A, B, C, -1});
        va.emplace_back(A);
        vb.emplace_back(B);
        vc.emplace_back(C);
    }

    std::vector<int> ans(Q);
    for (int i = 0; i < Q; ++i) {
        int A, B, C;
        std::cin >> A >> B >> C;
        vv.push_back({A, B, C, i});
        va.emplace_back(A);
        vb.emplace_back(B);
        vc.emplace_back(C);
    }

    std::sort(va.begin(), va.end());
    va.erase(std::unique(va.begin(), va.end()), va.end());
    std::sort(vb.begin(), vb.end());
    vb.erase(std::unique(vb.begin(), vb.end()), vb.end());
    std::sort(vc.begin(), vc.end());
    vc.erase(std::unique(vc.begin(), vc.end()), vc.end());

    for (int i = 0; i < N + Q; ++i) {
        vv[i][0] = int(std::lower_bound(va.begin(), va.end(), vv[i][0]) - va.begin());
        vv[i][1] = int(std::lower_bound(vb.begin(), vb.end(), vv[i][1]) - vb.begin());
        vv[i][2] = int(std::lower_bound(vc.begin(), vc.end(), vv[i][2]) - vc.begin());
    }

    std::sort(vv.begin(), vv.end(), [&](auto lhs, auto rhs) {
        if (lhs[0] != rhs[0]) {
            return lhs[0] < rhs[0];
        } else {
            return lhs[3] > rhs[3];
        }
    });

    debug(vv);

    fenwick fen(N + Q);
    std::vector<std::array<int, 4>> aux(N + Q);

    auto solve = [&](auto&& self, int l, int r) -> void {
        if (l + 1 == r) {
            return;
        }
        int mid = (l + r) >> 1;
        self(self, l, mid);
        self(self, mid, r);
        int p0 = l, p1 = mid, p2 = l;
        while (p0 != mid && p1 != r) {
            if (vv[p1][1] >= vv[p0][1]) {
                if (vv[p1][3] == -1) {
                    fen.modify(vv[p1][2], 1);
                } 
                aux[p2++] = vv[p1++];
            } else {
                if (vv[p0][3] != -1) {
                    ans[vv[p0][3]] += fen.get(vv[p0][2], N + Q - 1);
                } 
                aux[p2++] = vv[p0++];
            }
        }
        while (p0 != mid) {
            if (vv[p0][3] != -1) {
                ans[vv[p0][3]] += fen.get(vv[p0][2], N + Q - 1);
            } 
            aux[p2++] = vv[p0++];
        }
        while (p1 != r) {
            if (vv[p1][3] == -1) {
                fen.modify(vv[p1][2], 1);
            } 
            aux[p2++] = vv[p1++];
        }
        for (int i = mid; i < r; ++i) {
            if (vv[i][3] == -1) {
                fen.modify(vv[i][2], -1);
            }
        }
        for (int i = l; i < r; ++i) {
            vv[i] = aux[i];
        }
        debug(l, r, vv, ans);
    };
    solve(solve, 0, N + Q);

    for (int i = 0; i < Q; ++i) {
        std::cout << ans[i] << '\n';
    }

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