oj.uz

Submission #977834

# Submission time Handle Problem Language Result Execution time Memory
977834 2024-05-08T11:42:01 Z berr Passport (JOI23_passport) C++17
6 / 100
 398 ms 124916 KB 
#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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 324 ms 122352 KB Output is correct
5 Correct 398 ms 123804 KB Output is correct
6 Correct 376 ms 124916 KB Output is correct
7 Correct 283 ms 120992 KB Output is correct
8 Correct 214 ms 97816 KB Output is correct

Subtask #2
0 / 16.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 8.0

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

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 324 ms 122352 KB Output is correct
5 Correct 398 ms 123804 KB Output is correct
6 Correct 376 ms 124916 KB Output is correct
7 Correct 283 ms 120992 KB Output is correct
8 Correct 214 ms 97816 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 1 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -