Submission #1102531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102531		ShadowShark	Inspections (NOI23_inspections)	C++17	100 / 100	291 ms	33924 KiB

Main

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

const int maxN = 2e5 + 5;
long long tick[maxN], ans[maxN];
set<pair<int, int>> seg;
vector<pair<long long, int>> query;
int n, m, q;

bool cmp(pair<long long, int> A, pair<long long, int> B) {
    if (A.first != B.first) return A.first > B.first;
    return A.second < B.second;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> q;

    seg.insert({1, n});
    tick[1] = 1e18;

    long long curr = 1;
    for (int i = 1; i <= m; i++) {
        int L, R; bool kt = false;
        cin >> L >> R;

        /// Left side
        if (L > 1) {
            auto it = seg.lower_bound({L, L}); it--;
            auto [u, v] = *it;
            if (L <= v) {
                seg.erase(it);
                seg.insert({u, L - 1});
                if (v <= R) query.push_back({curr - (tick[u] + L - u) - 1, -1 * (v - L + 1)}); /// update L -> v
                else {
                    kt = true;
                    query.push_back({curr - (tick[u] + L - u) - 1, -1 * (R - L + 1)}); /// save from L -> R
                    seg.insert({R + 1, v}); tick[R + 1] = tick[u] + R + 1 - u;
                }
            }
        }

        if (!kt) {
            /// Middle
            auto it = seg.lower_bound({L, L});
            while (it != seg.end()) {
                auto [u, v] = *it;
                if (R < u) break;
                it = seg.erase(it);

                /// L <= u <= v <= R
                if (L <= u && v <= R) query.push_back({(curr + u - L) - tick[u] - 1, -1 * (v - u + 1)});
                else { /// L <= u <= R < v
                    /// u -> R
                    query.push_back({curr + u - L - tick[u] - 1, -1 * (R - u + 1)});
                    /// R + 1 -> v
                    seg.insert({R + 1, v});
                    tick[R + 1] = tick[u] + (R + 1) - u;
                    break ;
                }
            }
        }

        seg.insert({L, R});
        tick[L] = curr; curr += R - L + 1;
    }

    for (int i = 1; i <= q; i++) {
        long long s;
        cin >> s;

        query.push_back({s, i});
    }

    sort(query.begin(), query.end(), cmp);

    curr = 0;
    for (auto [s, id]: query) {
        if (id < 0) curr += abs(id);
            else ans[id] = curr;
    }

    for (int i = 1; i <= q; i++)
        cout << ans[i] << ' ';

    return 0;
}

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