Submission #927116

#	Time	Username	Problem	Language	Result	Execution time	Memory
927116		berr	Event Hopping (BOI22_events)	C++17	100 / 100	173 ms	48772 KiB

events

//ᓚᘏᗢ
 
#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 func =[&](int x, int y)->int{
        int h=0;
        if(x==y) return 0;
        if((v[y][1] <= v[x][1]&&v[y][1]>=v[x][0])) return h+(x==y?0:1);
        
        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((v[y][1] <= v[x][1]&&v[y][1]>=v[x][0])) return h+(x==y?0:1);

        if(x!=gh[x][0]&&gh[x][0]!=-1)x = gh[x][0], h++;
        
        if((v[y][1] <= v[x][1]&&v[y][1]>=v[x][0])) return h+(x==y?0:1);

        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 (stderr)

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;
      |                ~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30