Submission #805533

#	Time	Username	Problem	Language	Result	Execution time	Memory
805533		winter0101	Event Hopping (BOI22_events)	C++14	100 / 100	223 ms	24756 KiB

events

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
pii a[maxn];
int st[maxn][19];
int n,q;
pii st1[maxn*8];
pii combine(const pii &p1, const pii &q1){
if (p1.fi>q1.fi)return q1;
return p1;
}
void build(int id,int l,int r){
st1[id]={maxn*2,0};
if (l==r)return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u,pii val){
if (l>u||r<u)return;
if (l==r){
    st1[id]=combine(st1[id],val);
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st1[id]=combine(st1[id*2],st1[id*2+1]);
}
pii get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return {maxn*2,0};
if (u<=l&&r<=v)return st1[id];
int mid=(l+r)/2;
return combine(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void build(){
int m=n*2;
build(1,1,m);
for1(i,1,n){
update(1,1,m,a[i].se,{a[i].fi,i});
}
for1(i,1,n){
pii tmp=get(1,1,m,a[i].fi,a[i].se);
//if (i==64571)cout<<tmp.fi<<" "<<a[i].fi<<'\n';
if (tmp.fi>=a[i].fi)continue;
st[i][0]=tmp.se;
}
for1(j,1,18){
for1(i,1,n){
st[i][j]=st[st[i][j-1]][j-1];
}
}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("events.INP","r",stdin);
    //freopen("events.OUT","w",stdout);
    cin>>n>>q;
    vector<int>nen;
    nen.pb(0);
    for1(i,1,n){
    cin>>a[i].fi>>a[i].se;
    nen.pb(a[i].fi);
    nen.pb(a[i].se);
    }
    sort(all(nen));
    map<int,int>n1;
    for1(i,1,sz(nen)-1){
    if (nen[i]==nen[i-1])continue;
    n1[nen[i]]=n1[nen[i-1]]+1;
    }
    for1(i,1,n){
    a[i].fi=n1[a[i].fi];
    a[i].se=n1[a[i].se];
    //cout<<"type "<<" "<<a[i].fi<<" "<<a[i].se<<'\n';
    }
    build();
    for1(i,1,q){
    int s,e;
    cin>>s>>e;
    //if (i!=13)continue;
    if (a[s].se>a[e].se){
        cout<<"impossible"<<'\n';
    }
    else if (s==e){
        cout<<0<<'\n';
    }
    else if (a[e].fi<=a[s].se&&a[s].se<=a[e].se){
        cout<<1<<'\n';
    }
    else {
        int ans=0;
        for2(j,18,0){
        if (!st[e][j])continue;
        int id=st[e][j];
        if (a[id].fi>a[s].se){
            //cerr<<j<<'\n';
            e=id;
            ans+=(1<<j);
        }
        }
        //cerr<<st[e][0]<<'\n';
        //cout<<e<<'\n';
        //cout<<a[s].fi<<" "<<a[s].se<<'\n';
        //cout<<get(1,1,2*n,a[e].fi,a[e].se).fi<<" "<<a[e].fi<<'\n';
        if (st[e][0]==0)ans=-1;
        else {
            int id=st[e][0];
            if (a[id].fi<=a[s].se){
                ans+=2;
            }
            else ans=-1;
        }
        if (ans==-1)cout<<"impossible"<<'\n';
        else cout<<ans<<'\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