제출 #1282883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282883		MisterReaper	Inspections (NOI23_inspections)	C++20	100 / 100	235 ms	26084 KiB

Main

// File inspections.cpp created on 24.10.2025 at 10:02:20
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

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

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

    std::vector<std::array<int, 2>> T(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> T[i][0] >> T[i][1];
        --T[i][0], --T[i][1];
    }

    std::vector<i64> qry(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> qry[i];
    }

    std::set<std::array<i64, 3>> s;
    s.insert({0, N - 1, -inf});

    i64 now = 0;

    std::vector<std::array<i64, 2>> add;
    for (int i = 0; i < M; ++i) {
        auto it = --s.lower_bound({T[i][0] + 1, 0, 0});
        auto[l, r, t] = *it;
        if (l <= T[i][0] && T[i][1] <= r) {
            if (t >= 0) {
                add.push_back({now - (t + T[i][0] - l), T[i][1] - T[i][0] + 1});
            }
            it = s.erase(it);
            if (l != T[i][0]) {
                s.insert({l, T[i][0] - 1, t});
            }
            if (r != T[i][1]) {
                s.insert({T[i][1] + 1, r, t + T[i][1] + 1 - l});
            }
        } else {
            i64 cur = now;
            it = s.erase(it);
            if (t >= 0) {
                add.push_back({now - (t + T[i][0] - l), r - T[i][0] + 1});
            }
            if (l != T[i][0]) {
                it = ++(s.insert({l, T[i][0] - 1, t}).first);
            }
            cur += r - T[i][0] + 1;
            while (it != s.end()) {
                auto[ll, rr, tt] = *it;
                if (rr < T[i][1]) {
                    if (tt >= 0) {
                        add.push_back({cur - tt, rr - ll + 1});
                    }
                    it = s.erase(it);
                    cur += rr - ll + 1;
                } else {
                    if (tt >= 0) {
                        add.push_back({cur - tt, T[i][1] - ll + 1});
                    }
                    it = s.erase(it);
                    if (T[i][1] != rr) {
                        s.insert({T[i][1] + 1, rr, tt + T[i][1] + 1 - ll});
                    }
                    break;
                }
            }
        }
        s.insert({T[i][0], T[i][1], now});
        now += T[i][1] - T[i][0] + 1;
        debug(i, s, add);
    }

    std::sort(add.begin(), add.end(), std::greater());

    debug(add);

    std::vector<int> ordq(Q);
    std::iota(ordq.begin(), ordq.end(), 0);
    std::sort(ordq.begin(), ordq.end(), [&](auto lhs, auto rhs) {
        return qry[lhs] > qry[rhs];
    });

    int p = 0;
    i64 sum = 0;
    std::vector<i64> ans(Q);

    for (auto iq : ordq) {
        while (p < int(add.size()) && add[p][0] > qry[iq]) {
            sum += add[p][1];
            p++;
        }
        ans[iq] = sum;
    }

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

    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 23 / 23