Submission #1247831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247831		wenbang	Inspections (NOI23_inspections)	C++20	100 / 100	345 ms	29820 KiB

Main

#include <iostream>
#include <map>
#include <vector>

#ifdef LOCAL
#include "print.h"
#else
template <typename... Args> inline void print(const Args&... args) {}
inline void                             newline() {}
#endif

using ll = long long;
#define endl      '\n'
#define FOR(i, n) for (int i = 0; i < n; i++)

using namespace std;

static const ll INF = (1LL << 60);

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    int n, m, q;
    cin >> n >> m >> q;
    vector<int> l(m + 1), r(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> l [i] >> r [i];
    }
    vector<ll> pref(m + 1, 0);
    for (int i = 1; i <= m; i++) {
        ll len   = r [i] - l [i] + 1;
        pref [i] = pref [i - 1] + len;
    }

    vector<ll> offset(m + 1, 0);
    for (int i = 1; i <= m; i++) {
        offset [i] = pref [i - 1] - (l [i] - 1);
    }

    // start: {end, last task}
    map<int, pair<int, int>> lastRun;
    lastRun [1] = {n, 0};

    auto split = [&](int x) {
        if (x > n) {
            return lastRun.end();
        }
        auto it = lastRun.upper_bound(x);
        it--;
        int start = it->first;
        int end   = it->second.first;
        int last  = it->second.second;
        if (start == x) {
            return it;
        }
        if (end < x) {
            return next(it);
        }
        lastRun.erase(it);
        lastRun [start] = {x - 1, last};
        lastRun [x]     = {end, last};
        return lastRun.find(x);
    };

    vector<pair<ll, ll>> events;
    events.reserve(m * 2);

    for (int j = 1; j <= m; j++) {
        int  left = l [j], right = r [j];
        auto itR = split(right + 1);
        auto itL = split(left);

        for (auto it = itL; it != itR; ++it) {
            int start = it->first;
            int end   = it->second.first;
            int last  = it->second.second;
            if (last != 0) {
                ll weight = end - start + 1;
                ll g      = offset [j] - offset [last] - 1;
                events.emplace_back(g, weight);
            }
        }
        lastRun.erase(itL, itR);
        lastRun [left] = {right, j};
    }
    sort(events.begin(), events.end(), [&](auto& a, auto& b) {
        return a.first < b.first;
    });

    int        numEvents = events.size();
    vector<ll> suffix(numEvents + 1, 0);
    for (int i = numEvents - 1; i >= 0; i--) {
        suffix [i] = suffix [i + 1] + events [i].second;
    }

    vector<ll> ans(q);
    FOR(i, q) {
        ll s;
        cin >> s;
        int ind = lower_bound(
                      events.begin(), events.end(), pair<ll, ll>(s, -INF),
                      [&](auto& a, auto& b) {
                          return a.first < b.first;
                      }
                  ) -
                  events.begin();
        cout << suffix [ind] << (i + 1 < q ? ' ' : '\n');
    }
}

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