제출 #1315112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315112		baodat	Inspections (NOI23_inspections)	C++20	100 / 100	267 ms	25136 KiB

Main

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

struct Node {
    int r;
    long long v; // d value
};

static const long long UNDEF = (1LL << 62);

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

    int n, m, q;
    cin >> n >> m >> q;

    map<int, Node> mp;                 // start -> {end, d}
    mp[1] = Node{n, UNDEF};            // initially never run

    vector<pair<long long, long long>> gaps; // (gap, count)

    auto split = [&](int pos) -> map<int, Node>::iterator {
        if (pos > n) return mp.end();
        auto it = mp.lower_bound(pos);
        if (it != mp.end() && it->first == pos) return it;
        --it; // interval containing pos
        int l = it->first;
        int r = it->second.r;
        long long v = it->second.v;
        if (pos > r) return mp.end(); // should not happen
        it->second.r = pos - 1;
        return mp.emplace(pos, Node{r, v}).first;
    };

    auto assignRange = [&](int L, int R, long long newV) {
        auto itR = split(R + 1);
        auto itL = split(L);

        for (auto it = itL; it != itR; ++it) {
            long long oldV = it->second.v;
            if (oldV != UNDEF) {
                long long gap = newV - oldV - 1; // >= 0
                long long cnt = (long long)it->second.r - it->first + 1;
                gaps.emplace_back(gap, cnt);
            }
        }

        mp.erase(itL, itR);

        auto it = mp.emplace(L, Node{R, newV}).first;

        // merge with previous
        if (it != mp.begin()) {
            auto prv = prev(it);
            if (prv->second.v == it->second.v && prv->second.r + 1 == it->first) {
                prv->second.r = it->second.r;
                mp.erase(it);
                it = prv;
            }
        }
        // merge with next
        auto nxt = next(it);
        if (nxt != mp.end() && nxt->second.v == it->second.v && it->second.r + 1 == nxt->first) {
            it->second.r = nxt->second.r;
            mp.erase(nxt);
        }
    };

    long long T = 0; // days completed so far
    for (int i = 0; i < m; i++) {
        int L, R;
        cin >> L >> R;
        long long newD = (T + 1) - (long long)L; // d = lastDay - x
        assignRange(L, R, newD);
        T += (long long)(R - L + 1);
    }

    vector<long long> s(q);
    for (int i = 0; i < q; i++) cin >> s[i];

    // Combine equal gaps
    sort(gaps.begin(), gaps.end());
    vector<long long> gval, pref;
    gval.reserve(gaps.size());
    pref.reserve(gaps.size());

    long long total = 0;
    for (size_t i = 0; i < gaps.size(); ) {
        size_t j = i;
        long long gv = gaps[i].first;
        long long cnt = 0;
        while (j < gaps.size() && gaps[j].first == gv) {
            cnt += gaps[j].second;
            j++;
        }
        gval.push_back(gv);
        total += cnt;
        pref.push_back(total);
        i = j;
    }

    auto count_ge = [&](long long x) -> long long {
        auto it = lower_bound(gval.begin(), gval.end(), x);
        if (it == gval.end()) return 0;
        int idx = (int)(it - gval.begin());
        long long before = (idx == 0 ? 0 : pref[idx - 1]);
        return total - before;
    };

    for (int i = 0; i < q; i++) {
        if (i) cout << ' ';
        cout << count_ge(s[i]);
    }
    cout << '\n';
    return 0;
}

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