Submission #1034761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034761		happy_node	Event Hopping (BOI22_events)	C++17	100 / 100	429 ms	65716 KiB

events

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5;

int N,Q;

int L[MX], R[MX];
int up[MX][20];

map<int,int> id;

vector<pair<int,int>> open[MX], cl[MX];

struct segtree {
        pair<int,int> t[4*MX];
        set<pair<int,int>> S[MX];

        void upd(int v, int l, int r, int pos) {
                if(pos<l || r<pos) return;
                if(l==r) {
                        t[v]=*S[l].begin();
                        return;
                }
                int m=(l+r)/2;
                upd(v*2+0,l,m+0,pos);
                upd(v*2+1,m+1,r,pos);
                t[v]=min(t[v*2+0],t[v*2+1]);
        }

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

        void add(int p, pair<int,int> val) {
                S[p].insert(val);
                upd(1,1,2*N,p);
        }

        void del(int p, pair<int,int> val) {
                S[p].erase(val);
                upd(1,1,2*N,p);
        }

        void prep() {
                for(int i=1;i<MX;i++) {
                        S[i].insert({1e9,1e9});
                }
                for(int i=1;i<4*MX;i++) {
                        t[i]={1e9,1e9};
                }
        }
} st;

int main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

        cin>>N>>Q;        

        for(int i=1;i<=N;i++) {
                cin>>L[i]>>R[i];
                id[L[i]]=0;
                id[R[i]]=0;
        }

        int cnt=1;
        for(auto &[x,y]:id) y=cnt++;

        for(int i=1;i<=N;i++) {
                L[i]=id[L[i]];
                R[i]=id[R[i]];
                open[R[i]].push_back({L[i],i});
                cl[L[i]].push_back({R[i],i});
        }

        st.prep();

        for(int r=2*N;r>=1;r--) {
                for(auto [l,id]:open[r]) {
                        st.add(r,make_pair(l,id));
                }

                for(auto [R,id]:cl[r]) {
                        st.del(R,make_pair(r,id));
                        int qry=st.que(1,1,2*N,r,R).second;
                        if(qry!=1e9) up[id][0]=qry;
                        st.add(R,make_pair(r,id));
                }

                for(auto [R,id]:cl[r]) {
                        st.del(R,make_pair(r,id));
                }
        }

        for(int k=0;k+1<20;k++) {
                for(int i=1;i<=N;i++) {
                        if(up[i][k]!=0 && up[up[i][k]][k]!=up[i][k])
                                up[i][k+1]=up[up[i][k]][k];
                }
        }

        for(int i=0;i<Q;i++) {
                int s,e;
                cin>>s>>e;

                if(s==e) {
                        cout<<0<<'\n';
                        continue;
                }

                int cur=e, res=0;

                for(int k=19;k>=0;k--) {
                        if(up[cur][k]!=0 && L[up[cur][k]]>R[s]) {
                                cur=up[cur][k];
                                res+=1<<k;
                        }
                }

                if(L[cur]<=R[s] && R[s]<=R[cur]) {
                        res++;
                        cout<<res<<'\n';
                        continue;
                } 

                cur=up[cur][0];
                res++;

                if(L[cur]<=R[s] && R[s]<=R[cur]) {
                        res++;
                        cout<<res<<'\n';
                } else {
                        cout<<"impossible"<<'\n';
                }
        }
}

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