Submission #949775

#	Time	Username	Problem	Language	Result	Execution time	Memory
949775		Dec0Dedd	Event Hopping (BOI22_events)	C++14	100 / 100	487 ms	53904 KiB

events

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N  = 2e5+100;
const int INF = 1e9+10;
const int K = 20;

struct segtree {
    vector<pii> t;

    void init(int sz) {
        t.resize(4*sz+10);
        for (auto &u : t) u={INF, -INF};
    }

    void upd(int v, int l, int r, int p, pii x) {
        if (l == r) {
            t[v]=min(t[v], x);
            return;
        } int m=(l+r)/2;
        if (p <= m) upd(2*v, l, m, p, x);
        else upd(2*v+1, m+1, r, p, x);
        t[v]=min(t[2*v], t[2*v+1]);
    }

    pii que(int v, int l, int r, int ql, int qr) {
        if (l > qr || r < ql) return {INF, -INF};
        if (l >= ql && r <= qr) return t[v];
        int m=(l+r)/2;
        return min(que(2*v, l, m, ql, qr), que(2*v+1, m+1, r, ql, qr));
    }
};

int s[N], e[N], p[N], n, q, up[K][N];

vector<int> G[N];

void pre(int v, int pr) {
    up[0][v]=pr;
    for (int i=1; i<K; ++i) up[i][v]=up[i-1][up[i-1][v]];
    for (auto u : G[v]) pre(u, v);
}

void solve() {
    cin>>n>>q;

    set<int> st;
    for (int i=1; i<=n; ++i) {
        cin>>s[i]>>e[i];
        st.insert(s[i]), st.insert(e[i]);
    }

    map<int, int> sc; int i=1;
    for (auto u : st) sc[u]=i++;
    for (int i=1; i<=n; ++i) s[i]=sc[s[i]], e[i]=sc[e[i]];

    segtree tr; tr.init(N);
    for (int i=1; i<=n; ++i) tr.upd(1, 1, N, e[i], {s[i], i});

    for (int i=1; i<=n; ++i) {
        pii x=tr.que(1, 1, N, s[i], e[i]);
        if (x.first >= s[i]) p[i]=i;
        else p[i]=x.second;
        if (p[i] != i) G[p[i]].push_back(i);
    }

    for (int i=1; i<=n; ++i) {
        if (p[i] == i) {
            pre(i, i);
        }
    }

    while (q--) {
        int l, r; cin>>l>>r;

        if (l == r) {
            cout<<0<<"\n";
            continue;
        }

        int ans=0;
        for (int i=K-1; i>=0; --i) {
            if (i > 0 && up[i][r] == up[i-1][r]) continue;
            if (s[up[i][r]] > s[l]) ans+=(1<<i), r=up[i][r];
        }

        //cout<<"HERE "<<r<<"\n";
        if (s[r] <= e[l] && e[l] <= e[r]) cout<<ans+1<<"\n";
        else {
            r=up[0][r], ++ans;
            if (s[r] <= e[l] && e[l] <= e[r]) cout<<ans+1<<"\n";
            else cout<<"impossible\n";
        }
    }
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

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