Submission #579660

#	Time	Username	Problem	Language	Result	Execution time	Memory
579660		wdjpng	Event Hopping (BOI22_events)	C++17	25 / 100	259 ms	31556 KiB

events

    #include <bits/stdc++.h>
     
     
    #define int long long
    #define rep(i,n) for(int i = 0; i < n; i++)
    #define per(i,n) for(int i = n-1; i >=0; i--)
    #define all(a) a.begin(), a.end()
    #define pii pair<int,int>
     
    using namespace std;
     
    vector<pii>T(5e5,{1e15,-1});
    pii update(int i, int l, int r, int ui, pii uv)
    {
        if(r<=ui||l>ui) return T[i];
        if(l+1==r) return T[i]=min(T[i],uv);
     
        return T[i] = min(update(2*i,l,(l+r)/2,ui,uv),update(2*i+1,(l+r)/2,r,ui,uv));
    }
     
    pii query(int i, int l, int r, int ql, int qr)
    {
        if(qr<=l||r<=ql) return {1e15,-1};
        if(l>=ql&&r<=qr) return T[i];
        return min(query(2*i,l,(l+r)/2,ql,qr),query(2*i+1,(l+r)/2,r,ql,qr));
    }
     
    struct ev {int s,e;};
    bool path(ev a, ev b)
    {
        return b.s<=a.e&&b.e>=a.e;
    }
     
    signed main()
    {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
     
        int n,q;
        cin>>n>>q;
        vector<ev>evs(n);
        for(auto& e: evs) cin>>e.s>>e.e;
        vector<int>cords;
        for(ev e : evs) {cords.push_back(e.s); cords.push_back(e.e);}
        sort(all(cords));
        cords.erase(unique(all(cords)), cords.end());
        for(ev& e : evs) 
        {
            e.s=lower_bound(all(cords),e.s)-cords.begin();
            e.e=lower_bound(all(cords),e.e)-cords.begin();
        }
     
        rep(i,n) update(1,0,cords.size(), evs[i].e, {evs[i].s,i});
     
        vector<vector<int>>up(n, vector<int>(20));
        rep(i,n)
        {
            up[i][0]=query(1,0,cords.size(),evs[i].s,evs[i].e+1).second;
            if(up[i][0]==-1) up[i][0]=i;
        }
     
        for(int j = 1; j < 20; j++) rep(i,n) up[i][j]=up[up[i][j-1]][j-1];
     
        rep(cq,q)
        {
            int s,e;
            cin>>s>>e;
            s--; e--;
     
            int sum = 0;
            int v = e;
            for(int j = 19; j>=0;j--) if(evs[up[v][j]].s>evs[s].e) {v=up[v][j]; sum+=1<<j;}
            if(evs[v].s>evs[s].e) {sum++; v=up[v][0];}
            if(!path(evs[s], evs[v])) cout<<"impossible\n";
            else {
                if(s!=v) sum++;
                cout<<sum<<'\n';
            }
        }
    }

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