Submission #579650

#	Time	Username	Problem	Language	Result	Execution time	Memory
579650		wdjpng	Event Hopping (BOI22_events)	C++17	25 / 100	284 ms	28464 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(3e5,{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 = 20; 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