oj.uz

Submission #841664

# Submission time Handle Problem Language Result Execution time Memory
841664 2023-09-01T19:47:37 Z kwongweng Inspections (NOI23_inspections) C++17
0 / 100
 28 ms 238172 KB 
#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, int 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-1,i);
    }
    FOR(i,0,q) cout<<ans[i]<<" ";
    cout<< "\n";
    return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 238164 KB Output is correct
2 Correct 28 ms 238164 KB Output is correct
3 Incorrect 27 ms 238164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 238164 KB Output is correct
2 Correct 28 ms 238164 KB Output is correct
3 Incorrect 27 ms 238164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 238164 KB Output is correct
2 Incorrect 28 ms 238172 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 238164 KB Output is correct
2 Correct 28 ms 238164 KB Output is correct
3 Incorrect 27 ms 238164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 238164 KB Output is correct
2 Correct 28 ms 238164 KB Output is correct
3 Incorrect 27 ms 238164 KB Output isn't correct
4 Halted 0 ms 0 KB -