oj.uz

Submission #961242

# Submission time Handle Problem Language Result Execution time Memory
961242 2024-04-11T18:39:39 Z anton Passport (JOI23_passport) C++17
6 / 100
 114 ms 10068 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 114 ms 9944 KB Output is correct
5 Correct 101 ms 10064 KB Output is correct
6 Correct 89 ms 10068 KB Output is correct
7 Correct 86 ms 9296 KB Output is correct
8 Correct 74 ms 8532 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 114 ms 9944 KB Output is correct
5 Correct 101 ms 10064 KB Output is correct
6 Correct 89 ms 10068 KB Output is correct
7 Correct 86 ms 9296 KB Output is correct
8 Correct 74 ms 8532 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -