Submission #1208514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208514		Ghulam_Junaid	Inspections (NOI23_inspections)	C++20	100 / 100	641 ms	40692 KiB

Main

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

typedef long long ll;

const ll N = 2e5 + 10;
ll n, m, q, day[N], l[N], r[N], last[N];
map<ll, ll> cnt;

ll get_day(ll i, ll x){
    return day[i] + x - l[i];
}

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

    cin >> n >> m >> q;
    set<pair<ll, ll>> st;
    st.insert({0, 0});
    st.insert({n + 1, 0});
    for (ll i = 1; i <= m; i ++){
        cin >> l[i] >> r[i];
        day[i + 1] = day[i] + (r[i] - l[i] + 1);

        auto it = st.upper_bound({l[i], -2});
        it--;

        vector<pair<ll, ll>> del, add;
        while ((*it).first <= r[i]){
            auto nxt = it;
            nxt++;

            if ((*nxt).first <= l[i]){
                it++;
                continue;
            }

            if ((*it).first >= l[i]){
                del.push_back(*it);
                if ((*nxt).first > r[i] + 1)
                    add.push_back({r[i] + 1, (*it).second});
            }
            else{
                if ((*nxt).first > r[i] + 1)
                    add.push_back({r[i] + 1, (*it).second});
            }

            // cout << "Reaching " << (*it).first << endl;
            if ((*it).second <= 0){
                it++;
                continue;
            }

            ll llersection = min(r[i], (*nxt).first - 1) - max(l[i], (*it).first) + 1;
            ll common = l[i];
            if ((*it).first >= l[i])
                common = (*it).first;
            ll diff = get_day(i, common) - get_day((*it).second, common);

            // cout << "Add " << llersection << " in " << diff << endl;
            cnt[diff - 1] += llersection;

            it++;
        }
        add.push_back({l[i], i});

        for (auto P : del)
            st.erase(P);
        for (auto P : add)
            st.insert(P);
    }

    vector<pair<ll, ll>> vec;
    for (auto [x, c] : cnt){
        // cout << x << " : " << c << endl;
        vec.push_back({x, c});
    }
    sort(vec.begin(), vec.end());

    ll SZ = vec.size();
    ll suff[SZ + 5] = {};
    for (ll i = SZ - 1; i >= 0; i --){
        suff[i] = suff[i + 1] + vec[i].second;
        // cout << i << " :: " << vec[i].second << " " << suff[i] << endl;
    }

    for (ll i = 0; i < q; i ++){
        ll val;
        cin >> val;

        ll lb = lower_bound(vec.begin(), vec.end(), (pair<ll, ll>){val, -1}) - vec.begin();

        if (lb >= vec.size()) cout << "0 ";
        else cout << suff[lb] << " ";
    }
    cout << endl;
}

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