제출 #1269013

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269013		MisterReaper	Examination (JOI19_examination)	C++20	100 / 100	266 ms	12456 KiB

examination

// File A.cpp created on 11.09.2025 at 23:10:22
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/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::sync_with_stdio(false);
    std::cin.tie(nullptr);

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

    std::vector<int> ans(Q);
    std::vector<std::array<int, 4>> A(N + Q);
    for (int i = 0; i < N; ++i) {
        int X, Y;
        std::cin >> X >> Y;
        A[i] = {X, Y, X + Y, 1};
    }
    for (int i = 0; i < Q; ++i) {
        int X, Y, Z;
        std::cin >> X >> Y >> Z;
        A[N + i] = {X, Y, Z, -i};
    }

    std::vector<int> vals;
    for (int i = 0; i < N + Q; ++i) {
        vals.emplace_back(A[i][0]);
        vals.emplace_back(A[i][1]);
        vals.emplace_back(A[i][2]);
    }

    std::sort(vals.begin(), vals.end());
    vals.erase(std::unique(vals.begin(), vals.end()), vals.end());

    int nvals = int(vals.size());
    fenwick fen(nvals);

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

    std::sort(A.rbegin(), A.rend());

    debug(A);

    std::vector<std::array<int, 4>> tmp(N + Q);

    auto cdq = [&](auto&& self, int l, int r) -> void {
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        self(self, l, mid);
        self(self, mid + 1, r);
        int ptr0 = l, ptr1 = mid + 1, ptr2 = l;
        while (ptr0 != mid + 1 && ptr1 != r + 1) {
            if (A[ptr0][1] >= A[ptr1][1]) {
                tmp[ptr2++] = A[ptr0];
                if (A[ptr0][3] > 0) {
                    fen.modify(A[ptr0][2], +1);
                }
                ptr0++;
            } else {
                tmp[ptr2++] = A[ptr1];
                if (A[ptr1][3] <= 0) {
                    ans[-A[ptr1][3]] += fen.get(A[ptr1][2], nvals - 1);
                }
                ptr1++;
            }
        }
        while (ptr0 != mid + 1) {
            tmp[ptr2++] = A[ptr0];
            if (A[ptr0][3] > 0) {
                fen.modify(A[ptr0][2], +1);
            }
            ptr0++;
        }
        while (ptr1 != r + 1) {
            tmp[ptr2++] = A[ptr1];
            if (A[ptr1][3] <= 0) {
                ans[-A[ptr1][3]] += fen.get(A[ptr1][2], nvals - 1);
            }
            ptr1++;
        }
        for (int i = l; i <= mid; ++i) {
            if (A[i][3] > 0) {
                fen.modify(A[i][2], -1);
            }
        }
        for (int i = l; i <= r; ++i) {
            A[i] = tmp[i];
        }
        debug(l, r, ans);
    };
    cdq(cdq, 0, N + Q - 1);

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

    return 0;
}

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