Submission #595632

#	Time	Username	Problem	Language	Result	Execution time	Memory
595632		definitelynotmee	Event Hopping (BOI22_events)	C++98	30 / 100	114 ms	11336 KiB

events

    #include<bits/stdc++.h>
    #define ff first
    #define ss second
    #define all(x) x.begin(), x.end()
    using namespace std;
    using ll = long long;
    using pii = pair<int,int>;
    using pll = pair<ll,ll>;
    template<typename T>
    using matrix = vector<vector<T>>;
    const int INF = 1<<30;
     
    int main() {
        cin.tie(0)->sync_with_stdio(0);
     
        int n, q;
        cin >> n >> q;
        vector<pii> v(n);
        for(pii& i : v){
            cin >> i.ff >> i.ss;
            i.ff = INF-i.ff;
            i.ss = INF-i.ss;
            swap(i.ff,i.ss);
        }
        // cout << "----------\n";
        // for(pii i : v)
        //     cout << i.ff << ' ' << i.ss << '\n';
        // cout << "----------\n";
        vector<int>o(n);
        iota(all(o),0);
        sort(all(o),[&](int a, int b){
            return v[a] > v[b];
        });
     
        vector<int> jmp(n);
        vector<int> st;
     
        for(int i : o){
            int ini = 0, fim = st.size();
            while(ini!=fim){
                int m = (ini+fim)>>1;
                if(v[st[m]].ff <= v[i].ss)
                    fim = m;
                else ini = m+1;
            }
            if(ini == st.size()){
                jmp[i] = i;
            } else jmp[i] = st[ini];
            
            while(!st.empty() && v[st.back()].ss <= v[i].ss)
                st.pop_back();
            if(st.empty() || v[st.back()].ff > v[i].ff)
                st.push_back(i);
            // cout << i << ":\n";
            // for(int i : st)
            //     cout << i << ' ';
            // cout << '\n';
        }
     
        matrix<int> lift(20,vector<int>(n));
        for(int i = 0; i < n; i++){
            lift[0][i] = jmp[i]; 
            // cout << jmp[i] << ' ';
        }
        // cout << '\n';
        for(int i = 1; i < 20; i++){
            for(int j = 0; j < n; j++){
                lift[i][j] = lift[i-1][lift[i-1][j]];
            }
        }
        
        while(q--){
            int a, b;
            cin >> a >> b;
            a--, b--;
            swap(a,b);
            if(v[a] > v[b]){
                cout << "impossible\n";
                continue;
            }
            if(a == b){
                cout << 0 << '\n';
                continue;
            }
            if(v[a].ss >= v[b].ff){
                cout << 1 << '\n';
                continue;
            }
            int ct = 2;
            for(int i = 19; i >= 0; i--){
                if(v[lift[i][a]].ss < v[b].ff)
                    ct+=1<<i, a = lift[i][a];
            }
            a = lift[0][a];
            if(v[a].ss >= v[b].ff){
                cout << ct << '\n';
            } else {
                cout << "impossible\n";
            }
        }
     
    }

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             if(ini == st.size()){
      |                ~~~~^~~~~~~~~~~~

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