Submission #961242

#	Time	Username	Problem	Language	Result	Execution time	Memory
961242		anton	Passport (JOI23_passport)	C++17	6 / 100	114 ms	10068 KiB

passport

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define int long long

const int MAX_N =200000;
const int INF=  1e9;
pii inter[MAX_N];

struct minTree{
    vector<int> tr;
    int sz= 1;
    minTree(int len){
        while(sz<len){
            sz*=2;
        }
        tr.resize(2*sz, INF);
    }

    int get(int l, int r){
        //cout<<l<<" "<<r<<endl;
        l +=sz;
        r+=sz+1;
        int res= 1e18;

        for(; l<r; l/=2, r/=2){
            if(l%2 ==1){
                res= min(res, tr[l++]);
            }
            if(r%2 == 1){
                res = min(res, tr[--r]);
            }
        }
        return res;
    }
    void set(int id, int val){
        id+=sz;
        tr[id] = val;
        for(int i = id/2; i>=1; i/=2){
            tr[i] = min(tr[i*2], tr[i*2+1]);
        }
    }

};
signed main(){
    int n;
    cin>>n;

    for(int i = 0; i<n; i++){
        cin>>inter[i].first>>inter[i].second;
        inter[i].first--;
        inter[i].second--;
    }

    minTree dpr(n);
    dpr.set(n-1, 0);
    for(int i = n-2; i>=0; i--){
        int best=  dpr.get(i+1, inter[i].second);
        //cout<<best+1<<" ";
        dpr.set(i, best+1);
    }

    int q;
    cin>>q;

    for(int i = 0; i<q; i++){
        int v;
        cin>>v;
        v--;
        if(dpr.tr[dpr.sz] >= INF){
            cout<<-1<<endl;
        }
        else{
            cout<<dpr.tr[dpr.sz]<<endl;
        }
    }






}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46