Submission #970961

#	Time	Username	Problem	Language	Result	Execution time	Memory
970961		CSQ31	Inspections (NOI23_inspections)	C++17	100 / 100	281 ms	30152 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
//x - l_i + p_{i-1} - p_j + r_j - x
//(p_{i-1} - l_i+1) + (r_j - p_j) > s is the condition
//only r_j - p_j is important
struct range
{
    ll l,r,val = -1e18;
    range(){}
    range(ll _l,ll _r,ll _val){
        l = _l;
        r = _r;
        val = _val;
    }
    friend bool operator<(const range &a,const range &b){
        return b.r > a.r;
    }

};
set<range>s;
int main()
{
    owo
    int n,m,q;
    cin>>n>>m>>q;
    vector<PII>p(m),qs;
    vector<ll>pref(m,0);
    for(int i=0;i<m;i++){
        cin>>p[i].fi>>p[i].se;
        pref[i] = p[i].se - p[i].fi+1;
        if(i)pref[i]+=pref[i-1];
    }
    for(int i=0;i<q;i++){
        ll x;
        cin>>x;
        qs.pb({x,i});
    }
    sort(all(qs));
    vector<ll>ans(q,0);
    s.insert(range(1,n,-1e18));

    for(int i=0;i<m;i++){
        ll l0 = p[i].fi;
        ll r0 = p[i].se;
        vector<range>add;
        add.pb(range(l0,r0,r0 - pref[i]));
        while(true){
            auto it = s.ub(range(0,l0-1,0)); //first guy with r >= l0
            if(it == s.end())break;
            if(it->l > r0)break;
            if(it->l < l0)add.pb(range(it->l,l0-1,it->val));
            if(it->r > r0)add.pb(range(r0+1,it->r,it->val));

            ll inter = min(r0,it->r) - max(l0,it->l)+1;
            ll gap = (i?pref[i-1]:0) - l0 + it->val + 1;
            //cout<<"gap "<<inter<<" "<<gap<<'\n';
            int idx = lb(all(qs),make_pair(gap,0LL)) - qs.begin()-1;
            if(idx>=0)ans[idx] += inter;
            s.erase(it);
        }
        for(auto x:add)s.insert(x);
        /*
        cout<<"at "<<i<<'\n';
        for(auto x:s){
            cout<<x.l<<" "<<x.r<<" "<<x.val<<'\n';
        }*/
    }
    for(int i=q-2;i>=0;i--)ans[i]+=ans[i+1];
    vector<ll>fin(q);
    for(int i=0;i<q;i++)fin[qs[i].se] = ans[i];
    for(int i=0;i<q;i++)cout<<fin[i]<<" ";
    cout<<'\n';




}

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