Submission #927041

#	Time	Username	Problem	Language	Result	Execution time	Memory
927041		berr	Event Hopping (BOI22_events)	C++17	0 / 100	74 ms	26580 KiB

events

//≽^•⩊•^≼
 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
 
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, q; cin >> n >> q;
 
    vector<array<int, 2>> v(n);
    vector<vector<array<int, 2>>> qu(n);
    vector<array<int, 20>> gh(n);
    vector<int> id(n), ans(q, -1);
 
    for(auto &[i, l]: v) cin >> i >> l;
 
    iota(id.begin(), id.end(), 0);
    
    sort(id.begin(), id.end(), [&](int i, int j){
        return v[i] < v[j];
    });
    
    vector<int> el;
    
     for(int i=0; i<20; i++){
        for(int l=0; l<n; l++){
            gh[l][i]=l;
        }
    }

 
    for(int i=0; i<n; i++){
    /*   for(auto i: el) cout<<v[i][0]<<" "<<v[i][1]<<"\n";
            cout<<"\n";*/
        if(el.size()){
            int s=-1;
            
            for(int j=17; j>=0; j--){
                int tmp = (s+(1<<j));
                if(tmp >= el.size()) continue;
                if(v[el[tmp]][1]<v[id[i]][0]) s=tmp;
            }
 
            s++;
            if(s<el.size() && v[el[s]][1]>=v[id[i]][0]&&v[el[s]][1]<=v[id[i]][1]&&v[el[s]][0]<v[id[i]][0]){
                gh[id[i]][0]=el[s];
            }
 
        }
 
        if(el.size() && v[el.back()][1]<=v[id[i]][1]){
            while(el.size()&&v[el.back()][0]==v[id[i]][0])el.pop_back();
            el.push_back(id[i]);
        }
        else if(!el.size())el.push_back(id[i]);
    }
    el.clear();

    for(int i=1; i<20; i++){
        for(int l=0; l<n; l++){
            gh[l][i] = gh[gh[l][i-1]][i-1];
      
        }
    }   
    
    auto c = [&](int x, int y){
        return !(v[y][1] <= v[x][1]&&v[y][0]>=v[x][0]);
    };

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

        }

        if(x!=gh[x][0])
        x = gh[x][0], h++;

        if((v[y][1] <= v[x][1]&&v[y][0]>=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:45:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |                 if(tmp >= el.size()) continue;
      |                    ~~~~^~~~~~~~~~~~
events.cpp:50:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(s<el.size() && v[el[s]][1]>=v[id[i]][0]&&v[el[s]][1]<=v[id[i]][1]&&v[el[s]][0]<v[id[i]][0]){
      |                ~^~~~~~~~~~

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