Submission #987245

#	Time	Username	Problem	Language	Result	Execution time	Memory
987245		vjudge1	Inspections (NOI23_inspections)	C++17	100 / 100	398 ms	29236 KiB

Main

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

struct range {
    long long l, r, val = -1e18;
    range() {}
    range(long long _l, long long _r, long long _val) {
        l = _l;
        r = _r;
        val = _val;
    }
    friend bool operator<(const range& a, const range& b) {
        return b.r > a.r;
    }
};

set<range> s;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<pair<long long, long long>> p(m), qs;
    vector<long long> pref(m, 0);

    for (int i = 0; i < m; i++) {
        cin >> p[i].first >> p[i].second;
        pref[i] = p[i].second - p[i].first + 1;
        if (i) pref[i] += pref[i - 1];
    }

    for (int i = 0; i < q; i++) {
        long long x;
        cin >> x;
        qs.push_back({x, i});
    }

    sort(qs.begin(), qs.end());

    vector<long long> ans(q, 0);
    s.insert(range(1, n, -1e18));

    for (int i = 0; i < m; i++) {
        long long l0 = p[i].first;
        long long r0 = p[i].second;
        vector<range> add;
        add.push_back(range(l0, r0, r0 - pref[i]));

        while (true) {
            auto it = s.upper_bound(range(0, l0 - 1, 0));
            if (it == s.end()) break;
            if (it->l > r0) break;
            if (it->l < l0) add.push_back(range(it->l, l0 - 1, it->val));
            if (it->r > r0) add.push_back(range(r0 + 1, it->r, it->val));

            long long inter = min(r0, it->r) - max(l0, it->l) + 1;
            long long gap = (i ? pref[i - 1] : 0) - l0 + it->val + 1;
            int idx = lower_bound(qs.begin(), qs.end(), make_pair(gap, 0LL)) - qs.begin() - 1;
            if (idx >= 0) ans[idx] += inter;
            s.erase(it);
        }

        for (auto x : add) s.insert(x);
    }

    for (int i = q - 2; i >= 0; i--) ans[i] += ans[i + 1];
    vector<long long> fin(q);

    for (int i = 0; i < q; i++) fin[qs[i].second] = ans[i];

    for (int i = 0; i < q; i++) cout << fin[i] << " ";
    cout << '\n';
}

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