Submission #977834

#	Time	Username	Problem	Language	Result	Execution time	Memory
977834		berr	Passport (JOI23_passport)	C++17	6 / 100	398 ms	124916 KiB

passport

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
 
struct segtree{
    int n, tl, tr, type;
    vector<int> st, a;
 
    int merge(int x, int y){
        if(type==0) return min(x, y);
        return max(x, y);
    }
 
    segtree(vector<int> x, int t){
        n=x.size(); type = t;
        a=x; st.resize(2*n);
 
        for(int i=0; i<n; i++) st[i+n]=x[i];
 
        for(int i=n-1; i>=0; i--) st[i]=merge(st[i*2], st[i*2+1]);
    }
    int operator()(int l, int r){
        int base=a[l];
 
        for(l+=n, r+=n+1; l!=r; l/=2, r/=2){
            if(l&1) base=merge(base, st[l++]);
            if(r&1) base=merge(base, st[--r]);
        }
 
        return base;
    }
};
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    vector<int> l(n), r(n);

    for(int i=0; i<n; i++){
        cin >> l[i]>>r[i];
        l[i]--; r[i]--;
    }

    vector<vector<int>> left, right;
    left.push_back(l);
    right.push_back(r);
    vector<segtree> left_st, right_st;
 
    for(int i=1; i<=n; i*=2){
       segtree l(left.back(), 0), r(right.back(), 1);
       vector<int> l_new(n), r_new(n);
       for(int i=0; i<n; i++){
            l_new[i]=l(left.back()[i], right.back()[i]);
            r_new[i]=r(left.back()[i], right.back()[i]);
       }    
       left_st.push_back(l); right_st.push_back(r);
       left.push_back(l_new);
       right.push_back(r_new);
    }
 
    int qe; cin >> qe;
 
    while(qe--){
        int x; cin >> x;
        x--;
 
        int s=0;    
        int le=left[0][x], re=right[0][x], pos=-1, ans=0;

        for(int i=left.size()-1; i>=0; i--){
            int tl=left[i][x],  tr=right[i][x];
 
            if(tl==0&&tr==n-1)
                continue;
            else{
                le=tl; re=tr;
                pos=i; ans+=(1<<i);
                break;
            }
        }
        
            
        for(int i=pos-1; i>=0; i--){
            int vl=left_st[i](le, re), vr=right_st[i](le, re);

            if(vl ==0 && n-1==vr){
                continue;
            }
            else{
                le=min(vl, le); re=max(re, vr);
                ans+=(1<<i);
            }
        }

        ans++;

        int tl=(left_st[0](le, re));
        int tr=right_st[0](le, re);
        if(tl==0&&tr==n-1) cout<<ans<<"\n";
        else cout<<-1<<"\n";
    }   
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:68:13: warning: unused variable 's' [-Wunused-variable]
   68 |         int s=0;
      |             ^

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