Submission #828851

#	Time	Username	Problem	Language	Result	Execution time	Memory
828851		t6twotwo	Inspections (NOI23_inspections)	C++17	100 / 100	684 ms	37264 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> l(m), r(m);
    vector<ll> pfs(m + 1);
    vector<vector<pair<int, int>>> T(n + 1);
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i];
        l[i]--;
        T[l[i]].emplace_back(0, i);
        T[r[i]].emplace_back(1, i);
        pfs[i + 1] = pfs[i] + r[i] - l[i];
    }
    vector<ll> s(q);
    for (ll &x : s) {
        cin >> x;
    }
    vector<int> p(q);
    iota(p.begin(), p.end(), 0);
    sort(p.begin(), p.end(), [&](int i, int j) {
        return s[i] < s[j];
    });
    set<tuple<int, int, int>> t;
    auto get = [&](int x, int y) {
        return lower_bound(p.begin(), p.end(), pfs[y] - pfs[x + 1] + r[x] - l[y], [&](int i, ll j) {
            return s[i] < j;
        }) - p.begin();
    };
    vector<ll> f(q + 1);
    for (int i = 0; i <= n; i++) {
        for (auto [z, k] : T[i]) {
            if (z == 0) {
                auto it = t.upper_bound({k, -1, -1});
                if (it != t.begin() && it != t.end()) {
                    auto [i0, l0, r0] = *prev(it);
                    auto [i1, l1, r1] = *it;
                    assert(r0 == l1);
                    t.erase({i0, l0, r0});
                    t.erase({i1, l1, r1});
                    t.emplace(k, i, i);
                    t.emplace(i0, l0, i);
                    t.emplace(i1, i, r1);
                    f[get(i0, i1)] += i - r0;
                } else if (t.empty()) {
                    t.emplace(k, -1, -1);
                } else if (it == t.begin()) {
                    auto [i1, l1, r1] = *it;
                    t.erase(it);
                    t.emplace(k, -1, i);
                    t.emplace(i1, i, r1);
                } else {
                    auto [i0, l0, r0] = *prev(it);
                    t.erase(prev(it));
                    t.emplace(k, i, -1);
                    t.emplace(i0, l0, i);
                }
            } else {
                auto it = t.lower_bound({k, -1, -1});
                if (it != t.begin() && next(it) != t.end()) {
                    auto [_, l, r] = *it;
                    auto [i0, l0, r0] = *prev(it);
                    auto [i1, l1, r1] = *next(it);
                    assert(l == r0);
                    assert(r == l1);
                    f[get(i0, k)] += i - r0;
                    f[get(k, i1)] += i - l1;
                    t.erase(it);
                    t.erase({i0, l0, r0});
                    t.erase({i1, l1, r1});
                    t.emplace(i0, l0, i);
                    t.emplace(i1, i, r1);
                } else if (t.size() == 1) {
                    t.erase(it);
                } else if (it == t.begin()) {
                    auto [_, l, r] = *it;
                    auto [i1, l1, r1] = *next(it);
                    assert(r == l1);
                    f[get(k, i1)] += i - l1;
                    t.erase(it);
                    t.erase({i1, l1, r1});
                    t.emplace(i1, -1, r1);
                } else {
                    auto [_, l, r] = *it;
                    auto [i0, l0, r0] = *prev(it);
                    assert(l == r0);
                    f[get(i0, k)] += i - r0;
                    t.erase(it);
                    t.erase({i0, l0, r0});
                    t.emplace(i0, l0, -1);
                }
            }
        }
    }
    vector<ll> ans(q);
    for (int i = q - 1; i >= 0; i--) {
        ans[p[i]] = f[i + 1];
        f[i] += f[i + 1];
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << " \n"[i == q - 1];
    }
    return 6/22;
}

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