Submission #840902

#	Time	Username	Problem	Language	Result	Execution time	Memory
840902		kwongweng	Inspections (NOI23_inspections)	C++17	77 / 100	2072 ms	555840 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), lf(mxnode), rg(mxnode), sm(mxnode);
ll mxN = 1e12;

int ndcnt = 1;
int new_node(){
    ndcnt++; return ndcnt;
}

void update(int v, ll tl, ll tr, ll pos, ll num){
    if (tl==tr){sm[v] += num; return;}
    ll tm = (tl+tr)/2;
    if (pos <= tm){
        if (!lf[v]) lf[v] = new_node();
        update(lf[v], tl, tm, pos, num);
    }else{
        if (!rg[v]) rg[v] = new_node();
        update(rg[v], tm+1, tr, pos, num);
    }
    sm[v] = sm[lf[v]] + sm[rg[v]];
    //cout<<v<<" "<<tl<<" "<<tr<<" "<<sm[v]<<"\n";
}

ll get(int v, ll tl, ll tr, ll l, ll r){
    if (tl==l && tr==r) return sm[v];
    if (l>r) return 0;
    ll tm = (tl+tr)/2;
    ll ans = 0;
    if (lf[v]) ans += get(lf[v], tl, tm, l, min(r,tm));
    if (rg[v]) ans += get(rg[v], tm+1, tr, max(l,tm+1), r);
    return ans;
}

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";
            update(1,0,mxN,num,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, q; cin>>n>>m>>q;
    
    FOR(i,1,m+1){
        cin>>L[i]>>R[i];
        upd(1,1,n,L[i],R[i],i);
        s[i]=s[i-1] + (R[i]-L[i]+1);
    }
    //cout<<ndcnt<<"\n";
    while (q--){
        ll S; cin>>S;
        cout<<get(1,0,mxN,S+1, mxN)<<" ";
    }
    cout<< "\n";
    return 0;
}

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