제출 #1176007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176007		minhpk	Event Hopping (BOI22_events)	C++20	0 / 100	161 ms	52100 KiB

events

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,q;
pair<int,int> z[1000005];
vector <int> v;
struct node{
     int l,x;
};
node f[4000005];
node combine(node left, node right) {
    if (left.l < right.l) return left;
    if (left.l == right.l && left.x > right.x) return left;
    return right;
}
int bruh=1e16;
int up[100005][25];
int cost[100005][25];

void build (int id,int l,int r){
    if (l==r){
        f[id]={bruh,bruh};
        return;
    }
    int mid =(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    f[id]=combine(f[id*2],f[id*2+1]);
}

void update(int id,int l,int r,int pos,int x,int p){
    if (l==r){
        f[id]=combine(f[id],{x,p});
        return;
    }
    int mid =(l+r)/2;
    if (pos<=mid){
        update(id*2,l,mid,pos,x,p);
    }else{
        update(id*2+1,mid+1,r,pos,x,p);
    }
    f[id]=combine(f[id*2],f[id*2+1]);
}

node get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return {bruh,bruh};
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid =(l+r)/2;
    return combine( get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y) );
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> q;
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
         v.push_back(z[i].first);
         v.push_back(z[i].second);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int n=v.size();
    for (int i=1;i<=a;i++){
         z[i].first = lower_bound(v.begin(),v.end(),z[i].first)-v.begin()+1;
         z[i].second = lower_bound(v.begin(),v.end(),z[i].second)-v.begin()+1;
    }
    build(1,1,n);
    for (int i=1;i<=a;i++){
        update(1,1,n,z[i].second,z[i].first,i);
    }

    for (int i=1;i<=a;i++){
         node res= get(1,1,n,z[i].first,z[i].second);
         if (res.x==i){
             up[i][0]=i;
             cost[i][0]=0;
         }else{
             up[i][0]=res.x;
             cost[i][0]=1;
         }
    }

    for (int j=1;j<=22;j++){
        for (int i=1;i<=a;i++){
            up[i][j]=up[up[i][j-1]][j-1];
            cost[i][j]= cost[up[i][j-1]][j-1]+ cost[i][j-1];
        }
    }

    while (q--){
         int x,y;
         cin >> x >> y;
         if (z[x].first==z[y].first && z[x].second==z[y].second){
            cout << 0 << "\n";
            continue;
         }
         if (z[x].first>=z[y].second){
             cout << "impossible" << "\n";
             continue;
         }
         int p=y;
         int ans=0;
         for (int i=22;i>=0;i--){
                if (z[up[p][i]].first>z[x].second){
                    ans+= cost[p][i];
                    p=up[p][i];
                }
         }

         if (z[x].second>=z[p].first){
            cout << ans+1 << "\n";
            continue;
         }
         p=up[p][0];
         if (z[x].second>=z[p].first ){
            cout << ans+2 << "\n";
            continue;
         }
          p=up[p][0];
          if (z[x].second>=z[p].first ){
            cout << ans+3 << "\n";
            continue;
         }
         cout << "impossible" << "\n";
    }


    return 0;
}

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