Submission #1175407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175407		12345678	Event Hopping (BOI22_events)	C++20	20 / 100	211 ms	97212 KiB

events

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=17, inf=1e9;

struct segtree
{
    struct node
    {
        pair<int, int> mn;
        node *l, *r;
        node(pair<int, int> mn=make_pair(2e9, 0)): mn(mn), l(0), r(0) {}
    };
    typedef node* pnode;
    pnode rt;
    void update(int l, int r, pnode &k, int idx, pair<int, int> vl)
    {
        if (!k) k=new node();
        if (idx<l||r<idx) return;
        //cout<<"debug "<<l<<' '<<r<<'\n';
        if (l==r) return k->mn=min(k->mn, vl), void();
        int md=(l+r)/2;
        update(l, md, k->l, idx, vl);
        update(md+1, r, k->r, idx, vl);
        k->mn=min(k->l->mn, k->r->mn);
    }
    pair<int, int> query(int l, int r, pnode k, int ql, int qr)
    {
        if (qr<l||r<ql||!k) return {2e9, 0};
        if (ql<=l&&r<=qr) return k->mn;
        int md=(l+r)/2;
        return min(query(l, md, k->l, ql, qr), query(md+1, r, k->r, ql, qr));
    }
} d;

struct range
{
    int l, r, idx;
    range(int l, int r, int idx): l(l), r(r), idx(idx){}
    bool operator< (const range &o) const
    {
        if (r==o.r) return l<o.l;
        return r<o.r;
    }
};
vector<range> v;

int n, q, s[nx], e[nx], a, b, idx[nx], pa[nx][kx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=0; i<n; i++) cin>>s[i]>>e[i], v.push_back({s[i], e[i], i});
    sort(v.begin(), v.end());
    for (int i=0; i<n; i++) idx[v[i].idx]=i;
    for (int i=0; i<n; i++) d.update(1, inf, d.rt, v[i].r, {v[i].l, i});
    for (int i=0; i<n; i++) pa[i][0]=d.query(1, inf, d.rt, v[i].l, v[i].r).second;
    for (int i=1; i<kx; i++) for (int j=0; j<n; j++) pa[j][i]=pa[pa[j][i-1]][i-1];
    while (q--)
    {
        cin>>a>>b;
        a=idx[a-1], b=idx[b-1];
        if (a==b) cout<<"0\n";
        else if (v[a].r==v[b].r) cout<<"1\n";
        else if (b<a) cout<<"impossible\n";
        else
        {
            int res=0;
            for (int i=kx-1; i>=0; i--) if (pa[b][i]>a) b=pa[b][i], res+=(1<<i);
            //cout<<"v "<<a<<' '<<v[a].l<<' '<<v[a].r<<'\n';
            //cout<<"before "<<b<<' '<<v[b].l<<' '<<v[b].r<<'\n';
            if (v[b].l<=v[a].r&&v[a].r<=v[b].r) cout<<res+1<<'\n';
            else cout<<"impossible\n";
        } 
    }
}

/*
5 1
10 14
8 18
4 6
6 7
1 3
7 5
*/

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