oj.uz

Submission #920862

# Submission time Handle Problem Language Result Execution time Memory
920862 2024-02-03T06:42:25 Z Pacybwoah Event Hopping (BOI22_events) C++17
30 / 100
 460 ms 66068 KB 
#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;
        }
    }
    omg[16]=st(anc[16],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[j].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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 375 ms 65692 KB Output is correct
3 Correct 408 ms 65516 KB Output is correct
4 Correct 460 ms 65812 KB Output is correct
5 Correct 428 ms 65736 KB Output is correct
6 Correct 406 ms 65584 KB Output is correct
7 Correct 380 ms 65700 KB Output is correct
8 Correct 75 ms 65992 KB Output is correct
9 Correct 73 ms 65992 KB Output is correct
10 Correct 417 ms 65836 KB Output is correct
11 Correct 310 ms 65996 KB Output is correct
12 Correct 151 ms 65180 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Incorrect 2 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Incorrect 2 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 2 ms 856 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Incorrect 2 ms 860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 65948 KB Output is correct
2 Correct 408 ms 65480 KB Output is correct
3 Correct 449 ms 65500 KB Output is correct
4 Correct 72 ms 65996 KB Output is correct
5 Correct 417 ms 66068 KB Output is correct
6 Correct 405 ms 65752 KB Output is correct
7 Correct 405 ms 65996 KB Output is correct
8 Correct 381 ms 65908 KB Output is correct
9 Correct 195 ms 63948 KB Output is correct
10 Correct 372 ms 65348 KB Output is correct
11 Correct 270 ms 65268 KB Output is correct
12 Correct 385 ms 65228 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 375 ms 65692 KB Output is correct
3 Correct 408 ms 65516 KB Output is correct
4 Correct 460 ms 65812 KB Output is correct
5 Correct 428 ms 65736 KB Output is correct
6 Correct 406 ms 65584 KB Output is correct
7 Correct 380 ms 65700 KB Output is correct
8 Correct 75 ms 65992 KB Output is correct
9 Correct 73 ms 65992 KB Output is correct
10 Correct 417 ms 65836 KB Output is correct
11 Correct 310 ms 65996 KB Output is correct
12 Correct 151 ms 65180 KB Output is correct
13 Correct 0 ms 600 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 2 ms 980 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Incorrect 2 ms 860 KB Output isn't correct
19 Halted 0 ms 0 KB -