Submission #1311799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311799		12345678	Inspections (NOI23_inspections)	C++17	55 / 100	2095 ms	9392 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=2e5+5;

ll n, m, q, l, r, s, t, x;
vector<pair<ll, ll>> ins;
map<ll, pair<ll, ll>> mp;

void split(ll x)
{
    if (!x) return;
    auto itr=mp.lower_bound(x);
    if (itr->first==x) return;
    mp[x]={itr->second.first, itr->second.second-(itr->first-x)};
    itr->second.first=x+1;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    mp[n]={1, -1e18};
    for (int i=1; i<=m; i++)
    {
        cin>>l>>r;
        split(l-1);
        split(r);
        // for (auto x:mp) cout<<"mp "<<x.second.first<<' '<<x.first<<" : "<<x.second.second<<'\n';
        for (auto itr=mp.lower_bound(l); itr!=mp.end()&&itr->first<=r; itr=mp.erase(itr))
        {
            ll sz=itr->first-itr->second.first+1;
            t+=sz;
            ins.push_back({t-itr->second.second, sz});
        }
        mp[r]={l, t};
    }
    sort(ins.begin(), ins.end());
    // for (auto [x, y]:ins) cout<<"ins "<<x<<' '<<y<<'\n';
    for (int i=1; i<=q; i++)
    {
        cin>>x;
        ll sm=0;
        for (auto [t, sz]:ins) if (t<1e18&&t>x) sm+=sz;
        cout<<sm<<' ';
    }
}

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