oj.uz

Submission #844841

# Submission time Handle Problem Language Result Execution time Memory
844841 2023-09-06T03:46:37 Z Pacybwoah Event Hopping (BOI22_events) C++17
20 / 100
 340 ms 11280 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;
}
vector<int> seg;
void build(int l,int r,int ind,vector<int> &vec){
    if(l==r){
        if(vec[l-1]==-1) seg[ind]=1e9;
        else seg[ind]=vec[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]);
}
int query(int l,int r,int start,int end,int ind){
    if(r<start||end<l) return 1e9;
    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;
    } 
    seg.resize(4*n+4);
    for(int i=1;i<17;i++){
        build(1,n,1,anc[i-1]);
        for(int j=0;j<n;j++){
            if(anc[i-1][j]==-1) {
                anc[i][j]=-1;
                continue;
            }
            int tmp=query(1,n,anc[i-1][j]+1,j+1,1);
            if(tmp==1e9) anc[i][j]=-1;
            else anc[i][j]=tmp;
        }
    }
    /*or(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-1].end==vec[b-1].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=anc[j][b],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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 309 ms 10764 KB Output is correct
3 Correct 311 ms 10964 KB Output is correct
4 Correct 317 ms 10696 KB Output is correct
5 Correct 300 ms 10776 KB Output is correct
6 Correct 274 ms 10764 KB Output is correct
7 Correct 271 ms 10768 KB Output is correct
8 Correct 57 ms 11280 KB Output is correct
9 Correct 59 ms 11208 KB Output is correct
10 Correct 308 ms 11208 KB Output is correct
11 Incorrect 235 ms 11024 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Incorrect 2 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Incorrect 2 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Incorrect 2 ms 344 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 305 ms 10764 KB Output is correct
2 Correct 308 ms 10952 KB Output is correct
3 Correct 317 ms 10764 KB Output is correct
4 Correct 57 ms 11208 KB Output is correct
5 Correct 331 ms 11208 KB Output is correct
6 Correct 314 ms 10764 KB Output is correct
7 Correct 302 ms 10764 KB Output is correct
8 Correct 340 ms 11208 KB Output is correct
9 Correct 212 ms 10440 KB Output is correct
10 Correct 283 ms 10440 KB Output is correct
11 Correct 248 ms 10380 KB Output is correct
12 Correct 290 ms 10696 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 309 ms 10764 KB Output is correct
3 Correct 311 ms 10964 KB Output is correct
4 Correct 317 ms 10696 KB Output is correct
5 Correct 300 ms 10776 KB Output is correct
6 Correct 274 ms 10764 KB Output is correct
7 Correct 271 ms 10768 KB Output is correct
8 Correct 57 ms 11280 KB Output is correct
9 Correct 59 ms 11208 KB Output is correct
10 Correct 308 ms 11208 KB Output is correct
11 Incorrect 235 ms 11024 KB Output isn't correct
12 Halted 0 ms 0 KB -