Submission #721802

#	Time	Username	Problem	Language	Result	Execution time	Memory
721802		sunnat	Event Hopping (BOI22_events)	C++14	20 / 100	441 ms	17780 KiB

events

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
vector<int> l, r, si, ids;
vector<vector<int> > parent;
int n, q;
const int psize = 17;
struct Segment_Tree{
    vector<int> t;

    void build(int v, int l, int r){
        if(l == r){
            t[v] = si[l-1];
            return;
        }
        int m = (l + r) >> 1;
        build(v<<1, l, m);
        build(v<<1|1, m+1, r);
        t[v] = ::l[t[v<<1]] <= ::l[t[v<<1|1]] ? t[v<<1] : t[v<<1|1];
    }

    int get(int v, int l, int r, int L, int R){
        if(L == l && R == r) return t[v];
        int m = (l + r) >> 1;
        if(m < L) return get(v<<1|1, m+1, r, L, R);
        if(m >= R) return get(v<<1, l, m, L, R);
        int i = get(v<<1|1, m+1, r, m+1, R);
        int j = get(v<<1, l, m, L, m);
        return ::l[j] <= ::l[i] ? j : i;
    }

    int get(int l, int r){
        return ids[get(1, 1, n, l+1, r+1)];
    }

    void build(){
        t.resize(n<<2);
        build(1, 1, n);
    }
};

int main(){
    cin >> n >> q;
    l.resize(n);
    r.resize(n);
    si.resize(n);
    ids.resize(n);
    parent.resize(n, vector<int>(psize, -1));

    for(int i = 0; i < n; i ++){
        cin >> l[i] >> r[i];
        // r[i] --;
        si[i] = i;
    }
    sort(si.begin(), si.end(), [&](int r, int l){
        return ::r[r] != ::r[l] ? ::r[r] < ::r[l] : ::l[r] < ::l[r];
    });
    
    for(int i = 0; i < n; i ++) ids[si[i]] = i;
    
    Segment_Tree st;
    st.build();
    for(int i = 0, l, r, m; i < n; i ++){
        l = 0;
        r = i;
        while(l < r){
            m = (l + r) >> 1;
            if(::r[si[m]] >= ::l[si[i]]) r = m;
            else l = m + 1;
        }
        l = st.get(l, i);
        if(::l[si[l]] != ::l[si[i]]){
            parent[i][0] = l;
            for(int j = 1; j < psize; j ++){
                if(parent[parent[i][j-1]][j-1] != -1)
                    parent[i][j] = parent[parent[i][j-1]][j-1];
                else break;
            }
        }
    }

    for(int i = 0, u, v, cnt = 0; i < q; i ++){
        cin >> u >> v;
        u --;
        v --;
        if(u == v){
            cout << "0\n";
            continue;
        }
        if(l[v] <= r[u] && r[u] <= r[v]){
            cout << 1 << '\n';
            continue;
        }
        u = ids[u];
        v = ids[v];
        if(u > v){
            cout << "impossible\n";
            continue;
        }
        cnt = 0;
        for(int i = psize - 1; i >= 0; i --){
            if(parent[v][i] != -1 && l[si[parent[v][i]]] > r[si[u]]){
                cnt += 1<<i;
                v = parent[v][i];
            }
        }
        if(parent[v][0] == -1) cout << "impossible\n";
        else cout << cnt + 2 << "\n";
    }

    return 0;
}

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