Submission #1251943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251943		nasjes	Inspections (NOI23_inspections)	C++20	100 / 100	749 ms	32284 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>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 1e6+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m,k, t;
set<pair<pll, ll> > s;
ll ans=0;
map<ll, ll> mp;
void add(ll l, ll r, ll w){
    if(s.size()==0){
        s.insert({{l, r}, w});
        return;
    }
    auto it=s.lower_bound({{l+1, -inf}, -inf});
    if(it!=s.begin()){
        it--;
        pair<pll, ll> cur=(*it);
        if(cur.fi.se>=l) {
            if (cur.fi.se <= r) {
                ll t2 = (cur.se);
                ll dt = w - t2;
                dt = dt - (l - cur.fi.fi);
                mp[dt] += (cur.fi.se - l + 1);
                s.erase(cur);
                if (cur.fi.fi <= l - 1) s.insert({{cur.fi.fi, l - 1}, t2});
            } else {
                ll t2 = (cur.se);
                ll dt = w - t2 - (l - cur.fi.fi);
                ll len = (r - l + 1);
                mp[dt] += len;
                s.erase(cur);
                if (cur.fi.fi <= l - 1)s.insert({{cur.fi.fi, l - 1}, t2});
                s.insert({{r + 1, cur.fi.se}, t2 + (r - cur.fi.fi + 1)});
                s.insert({{l, r}, w});
                return;
            }
        }
    }
    if(s.size()==0){
        s.insert({{l, r}, w});
        return;
    }
    it=s.lower_bound({{l+1, -inf}, -inf});
    while(it!=s.end() && (*it).fi.se<=r){
        pair<pll, ll> cur=(*it);
        if(cur.fi.se<=r){
            ll t2=(cur.se);
            ll dx=cur.fi.fi-l;
            ll dt=w-t2+dx;
            ll len=cur.fi.se-cur.fi.fi+1;
            mp[dt]+=len;
            s.erase(cur);
        }
        it=s.lower_bound({{l+1, -inf}, -inf});
    }
    if(it!=s.end()){
        pair<pll, ll> cur=(*it);
        if(cur.fi.fi<=r){
            ll t2=(cur.se);
            ll dt=w-t2;
            dt+=(cur.fi.fi-l);
            ll len=r-cur.fi.fi+1;
            mp[dt]+=len;
            s.erase(cur);
            if(cur.fi.se>=r+1)s.insert({{r+1, cur.fi.se},  len+t2});
        }
    }
    s.insert({{l, r}, w});
}
int main() {

    ll  u,v, w, q, l, r;
    cin>>n>>m>>q;
    w=1;
    for(int i=1; i<=m; i++) {
        cin >> l >> r;

        add(l, r, w);
        w += (r - l + 1);
    }
    vector<pll> f;
    ll sum=0;
    for(auto x: mp){
        sum+=x.se;
        f.pb({x.fi, sum});
    }
    for(int i=1; i<=q; i++){
        cin>>v;
        ans=0;
        l=1;
        r=f.size();
        while(r-l>=1){
            ll mid=(l+r+1)/2;
            if(f[mid-1].fi<=v){
                l=mid;
            }
            else{
                r=mid-1;
            }
        }
        if(f.size()==0){
            cout<<0<<endl;
            continue;
        }
        ll x=f[l-1].se;
        if(v<f[l-1].fi)x=0;
        ans=sum-x;
        cout<<ans<<endl;
    }
    return 0;
}

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