Submission #921089

#	Time	Username	Problem	Language	Result	Execution time	Memory
921089		Pacybwoah	Event Hopping (BOI22_events)	C++17	100 / 100	446 ms	66760 KiB

events

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
struct event{
    int start,end,pos;
};
bool cmp(event a,event b){
    if(a.end==b.end) return a.start<b.start;
    return a.end<b.end;
}
struct st{
vector<pair<int,int> > seg;
st(vector<int> &vec,int n){
    seg.resize(4*n+4);
    build(1,n,1,vec);
}
void build(int l,int r,int ind,vector<int> &vec){
    if(l==r){
        if(vec[l-1]==-1) seg[ind]=make_pair(1e9+1,l-1);
        else seg[ind]=make_pair(vec[l-1],l-1);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ind*2,vec);
    build(mid+1,r,ind*2+1,vec);
    seg[ind]=min(seg[ind*2],seg[ind*2+1]);
}
pair<int,int> query(int l,int r,int start,int end,int ind){
    if(r<start||end<l) return make_pair(1e9+1,1e9+1);
    if(start<=l&&r<=end) return seg[ind];
    int mid=(l+r)>>1;
    return min(query(l,mid,start,end,ind*2),query(mid+1,r,start,end,ind*2+1));
}};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    vector<event> vec(n);
    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        vec[i].start=a;
        vec[i].end=b;
        vec[i].pos=i;
    }
    vector<int> ori(n+1);
    sort(vec.begin(),vec.end(),cmp);
    for(int i=0;i<n;i++) ori[vec[i].pos+1]=i;
    vector<vector<int> > anc(17,vector<int>(n));
    anc[0][0]=-1;
    //for(int i=0;i<n;i++) cout<<"\n"<<vec[i].start<<" "<<vec[i].end;
    for(int i=1;i<n;i++){
        if(vec[i-1].end<vec[i].start){
            anc[0][i]=-1;
            continue;
        }
        int l=0,r=i-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(vec[mid].end<vec[i].start){
                l=mid+1;
            }
            else{
                r=mid;
            }
        }
        anc[0][i]=l;
    } 
    vector<int> emp(1,1);
    vector<st> omg(17,st(emp,1));
    for(int i=1;i<17;i++){
        omg[i-1]=st(anc[i-1],n);
        for(int j=0;j<n;j++){
            if(anc[i-1][j]==-1) {
                anc[i][j]=-1;
                continue;
            }
            int tmp=omg[i-1].query(1,n,anc[i-1][j]+1,j+1,1).first;
            if(tmp==1e9+1) anc[i][j]=-1;
            else anc[i][j]=tmp;
        }
    }
    vector<int> bruv(n);
    for(int i=0;i<n;i++) bruv[i]=vec[i].start;
    omg[16]=st(bruv,n);
    /*for(int i=0;i<17;i++){
        for(int j=0;j<n;j++){
            cout<<anc[i][j]<<" ";
        }
        cout<<"\n";
    }*/
    for(int i=0;i<q;i++){
        cin>>a>>b;
        if(a==b){
            cout<<"0\n";
            continue;
        }
        a=ori[a],b=ori[b];
        if(vec[a].end==vec[b].end){
            cout<<"1\n";
            continue;
        }
        if(a>b){
            cout<<"impossible\n";
            continue;
        }
        int ans=0;
        for(int j=16;j>=0;j--){
            if(anc[j][b]>a&&anc[j][b]!=-1) b=omg[16].query(1,n,anc[j][b]+1,b+1,1).second,ans+=(1<<j);
        }
        if(anc[0][b]<=a&&anc[0][b]!=-1){
            cout<<ans+1<<"\n";
        }
        else cout<<"impossible\n";
    }
}
 
/*1 3
2 4
3 7
4 7
7 9*/

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