Submission #841668

#	Time	Username	Problem	Language	Result	Execution time	Memory
841668		kwongweng	Inspections (NOI23_inspections)	C++17	100 / 100	1370 ms	249816 KiB

Main

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

const int mxnode = 2e7+1,N = 2e5+1;
vi L(N), R(N), val(mxnode,-1);
vector<ll> s(N),  sm(mxnode);
vector<pair<ll,int>> S;
int q;

void update(int v, int tl, int tr, int l, int r, ll Val){
    if (tl==l && tr==r){
        sm[v] += Val; return;
    }
    if (l>r) return;
    int tm = (tl+tr)/2;
    update(2*v,tl,tm,l,min(r,tm), Val);
    update(2*v+1,tm+1,tr,max(l,tm+1),r,Val);
}

ll get(int v, int tl, int tr, int pos){
    if (tl==tr) return sm[v];
    int tm = (tl+tr)/2;
    if (pos <= tm) return sm[v] + get(2*v,tl,tm,pos);
    return sm[v] + get(2*v+1,tm+1,tr,pos);
}

void upd(int v, int tl, int tr, int l, int r, int ind){
    if (tl != tr && val[v] != -1){
        val[2*v]=val[2*v+1]=val[v];
    }
    if (l>r) return;
    if (tl==l && tr==r && (tl==tr || val[v] != -1)){
        if (val[v] != -1){
            ll num = s[ind-1] + (l-L[ind]) - s[val[v]-1] - (l-L[val[v]]);
            //cout<<val[v]<<" "<<ind<<" "<<num<<" "<<r-l+1<<"\n";
            int pos = lower_bound(S.begin(), S.end(), make_pair(num,0)) - S.begin();
            //cout<<pos<<" "<<num<<"\n";
            update(1,0,q,0,pos-1,r-l+1); 
        }
        val[v] = ind;
        return;
    }
    int tm = (tl+tr)/2;
    upd(2*v,tl,tm,l,min(r,tm),ind);
    upd(2*v+1,tm+1,tr,max(l,tm+1),r,ind);
    if (val[2*v] == val[2*v+1] && val[2*v] != -1) val[v]=val[2*v];
    else val[v]=-1;
}


int main(){
    int n, m; cin>>n>>m>>q;
    
    FOR(i,1,m+1){
        cin>>L[i]>>R[i];
    }
    //cout<<ndcnt<<"\n";
    FOR(i,0,q){
        ll val; cin>>val;
        S.pb({val,i});
    }
    sort(S.begin(), S.end());
    FOR(i,1,m+1){
        upd(1,1,n,L[i],R[i],i);
        s[i]=s[i-1]+(R[i]-L[i]+1);
    }
    vector<ll> ans(q);
    FOR(i,0,q){
        ans[S[i].se] = get(1,0,q,i);
    }
    FOR(i,0,q) cout<<ans[i]<<" ";
    cout<< "\n";
    return 0;
}

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