oj.uz

Submission #927107

# Submission time Handle Problem Language Result Execution time Memory
927107 2024-02-14T09:33:11 Z berr Event Hopping (BOI22_events) C++17
0 / 100
 175 ms 48756 KB 
//≽^•⩊•^≼
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
 
struct segtree{
    int n, tl, tr;
    vector<int> st, id;
    vector<array<int, 2>> gh;

    int base = 1e9+37;

    int merge(int x, int y){
        if(y==base) return x;
        if(x==base) return y;

        if(gh[x][0]!=gh[y][0]){
            if (gh[x][0]<=gh[y][0]) return x;
            return y;

        }
        if(gh[x][1] <= gh[y][1]) return x;
        return y;
    }

    segtree(int _n, vector<array<int, 2>> _gh, vector<int> a){
        n= _n;
        gh = _gh;
        id = a;
        st.resize(4*n);
        build(1, 0, n-1);
    }

    void build(int v, int l, int r){
        if(l==r) st[v] = id[l];
        else{
            int mid = (l + r) / 2;
            build(v*2, l, mid);
            build(v*2+1, mid+1, r);

            st[v] = merge(st[v*2], st[v*2+1]);
        }
    }

    int get(int v, int l, int r){
        if(l>tr || r < tl || r<l) return base;
        else if(l>=tl && r<= tr) return st[v];
        else{
            int mid = (l+r) / 2;
            return merge(get(v*2, l, mid), get(v*2+1, mid+1, r));
        }
    }

    int get(int l, int r){
        tl = l; tr = r;
        return get(1, 0, n-1);
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q; cin >> n >> q;
 
    vector<array<int, 2>> v(n), ve;
    vector<vector<array<int, 2>>> qu(n);
    vector<array<int, 20>> gh(n), ghh(n);
    vector<int> id(n), ans(q, -1);
        
    iota(id.begin(), id.end(), 0);

    for(auto &[i, l]: v) cin >> i >> l;
        ve = v;
    sort(id.begin(), id.end(), [&](int i, int j){
        if(ve[i][1]==ve[j][1]) return ve[i][0]<ve[j][0];
        return ve[i][1]<ve[j][1];
    });

    segtree st(n, ve, id);

     for(int i=0; i<20; i++){
        for(int l=0; l<n; l++){
            gh[l][i]=-1;
        }
    }

    for(int i=0; i<n; i++){
        int l=-1;

        for(int j=18; j>=0; j--){
            int tmp = l+(1<<j);
            if(tmp<ve.size() && ve[id[tmp]][1] < v[i][0]) l = tmp;
        }
        l++;

        int r=0;

        for(int j=18; j>=0; j--){
            int tmp = r+(1<<j);
            if(tmp<ve.size() && ve[id[tmp]][1] <= v[i][1]) r = tmp;
        }   

       // if(i==3)cout<<l<<" "<<r<<"uu\n";

      //  cout<<l<<" "<<r<<"\n";
        int h = st.get(l, r);
        //cout<<i<<" "<<h<<"\n";
        if(h>=n) gh[i][0]=-1;
        else gh[i][0] = h;
    }
    for(int i=1; i<20; i++){
        for(int l=0; l<n; l++){
            if(gh[l][i-1]==-1) gh[l][i]=-1;
            else gh[l][i] = gh[gh[l][i-1]][i-1];
      
        }
    }   
    
    auto c = [&](int x, int y){
        return v[x][0]>v[y][0];
    };
    auto a = [&](int x, int y){
        if(v[x][0]==v[y][0]) return v[y][1] > v[x][1];
        return v[x][0] > v[y][0];

       //return !(v[y][1] <= v[x][1]&&v[y][1]>=v[x][0]);
    };
    auto func =[&](int x, int y)->int{
        int h=0;
        if(x==y) return 0;
      //  cout<<x<<" "<<gh[x][0]<<"\n";
        for(int j=19; j>=0; j--){

            if(c(gh[x][j], y)&&gh[x][j]!=x){
                h+=(1<<j); x=gh[x][j];
                j++;
            }

        }

        if(x!=gh[x][0]&&gh[x][0]!=-1)x = gh[x][0], h++;
       // cout<<v[x][1]<<" "<<v[y][1]<<"\n";
        if((v[y][1] <= v[x][1]&&v[y][1]>=v[x][0])) return h+(x==y?0:1);
        return -1LL;
    };
 

 
    while(q--){
        int x, y; cin >> x >> y;
        x--; y--;
        int h = func(y, x);
        if(h==-1) cout<<"impossible";
        else cout<<h;
        cout<<"\n";        
    }


}

Compilation message

events.cpp: In function 'int main()':
events.cpp:95:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             if(tmp<ve.size() && ve[id[tmp]][1] < v[i][0]) l = tmp;
      |                ~~~^~~~~~~~~~
events.cpp:103:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             if(tmp<ve.size() && ve[id[tmp]][1] <= v[i][1]) r = tmp;
      |                ~~~^~~~~~~~~~
events.cpp:125:10: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  125 |     auto a = [&](int x, int y){
      |          ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 160 ms 46424 KB Output is correct
3 Correct 135 ms 46772 KB Output is correct
4 Correct 151 ms 48732 KB Output is correct
5 Correct 128 ms 48728 KB Output is correct
6 Correct 128 ms 48724 KB Output is correct
7 Correct 135 ms 48756 KB Output is correct
8 Correct 119 ms 48720 KB Output is correct
9 Correct 122 ms 48720 KB Output is correct
10 Correct 143 ms 48636 KB Output is correct
11 Incorrect 136 ms 48720 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.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 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Incorrect 1 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.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 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Incorrect 1 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.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 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Incorrect 1 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 46416 KB Output is correct
2 Correct 131 ms 46472 KB Output is correct
3 Correct 144 ms 48672 KB Output is correct
4 Correct 128 ms 48656 KB Output is correct
5 Correct 175 ms 48720 KB Output is correct
6 Incorrect 147 ms 48728 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 160 ms 46424 KB Output is correct
3 Correct 135 ms 46772 KB Output is correct
4 Correct 151 ms 48732 KB Output is correct
5 Correct 128 ms 48728 KB Output is correct
6 Correct 128 ms 48724 KB Output is correct
7 Correct 135 ms 48756 KB Output is correct
8 Correct 119 ms 48720 KB Output is correct
9 Correct 122 ms 48720 KB Output is correct
10 Correct 143 ms 48636 KB Output is correct
11 Incorrect 136 ms 48720 KB Output isn't correct
12 Halted 0 ms 0 KB -