Submission #1250961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250961		Geforgs	Inspections (NOI23_inspections)	C++20	100 / 100	411 ms	28352 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

void solve(){
    ll n, m, q, i, t=0, x, y, l, r, w;
    cin>>n>>m>>q;
    set<pair<pair<ll, ll>, ll>> s;
    s.insert({{0, n-1}, inf});
    vector<pair<ll, ll>> a;
    for(i=0;i<m;++i){
        cin>>l>>r;
        auto it = s.upper_bound({{l, n+1}, inf+1});
        --it;
        if(it->first.first < l){
            x = it->first.first;
            y = it->first.second;
            w = it->second;
            s.erase(it);
            s.insert({{x, l-1}, w});
            w += l - x;
            x = l;
            s.insert({{x, y}, w});
        }
        it = s.upper_bound({{r, n+1}, inf+1});
        --it;
        if(it->first.second > r){
            x = it->first.first;
            y = it->first.second;
            w = it->second;
            s.erase(it);
            s.insert({{x, r}, w});
            w += r + 1 - x;
            x = r + 1;
            s.insert({{x, y}, w});
        }
        vector<pair<pair<ll, ll>, ll>> del;
        for(it=s.lower_bound({{l, l}, 0});it != s.end() and it->first.first <= r;++it){
            del.pb(*it);
            x = it->first.first;
            y = it->first.second;
            w = t + x - l;
            a.pb({w - it->second, y - x + 1});
        }
        for(auto el: del){
            s.erase(el);
        }
        s.insert({{l, r}, t});
        t += r - l + 1;
    }
    sort(a);
    a.pb({inf, 0});
    for(i=a.size()-2;i>=0;--i){
        a[i].second += a[i+1].second;
    }
    for(i=0;i<q;++i){
        cin>>t;
        l = -1;
        r = a.size()-1;
        while(r - l > 1){
            m = (l+r)/2;
            if(a[m].first <= t){
                l = m;
            }else{
                r = m;
            }
        }
        cout<<a[r].second<<' ';
    }
    cout<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    return 0;
}

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