oj.uz

Submission #844853

# Submission time Handle Problem Language Result Execution time Memory
844853 2023-09-06T05:10:06 Z Pacybwoah Event Hopping (BOI22_events) C++17
20 / 100
 439 ms 63192 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) anc[i][j]=-1;
            else anc[i][j]=tmp;
        }
    }
    omg[16]=st(anc[16],n);
    /*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=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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 380 ms 62376 KB Output is correct
3 Correct 424 ms 62508 KB Output is correct
4 Correct 439 ms 62716 KB Output is correct
5 Correct 426 ms 62556 KB Output is correct
6 Correct 383 ms 62568 KB Output is correct
7 Correct 389 ms 62760 KB Output is correct
8 Correct 69 ms 63080 KB Output is correct
9 Correct 69 ms 62920 KB Output is correct
10 Correct 414 ms 62920 KB Output is correct
11 Incorrect 297 ms 62780 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 344 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Incorrect 2 ms 856 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 344 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Incorrect 2 ms 856 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 344 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Incorrect 2 ms 856 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 372 ms 62408 KB Output is correct
2 Correct 421 ms 62472 KB Output is correct
3 Correct 438 ms 62408 KB Output is correct
4 Correct 73 ms 63192 KB Output is correct
5 Correct 394 ms 62912 KB Output is correct
6 Correct 402 ms 62624 KB Output is correct
7 Correct 434 ms 62552 KB Output is correct
8 Correct 376 ms 62668 KB Output is correct
9 Correct 193 ms 61896 KB Output is correct
10 Correct 385 ms 62664 KB Output is correct
11 Correct 266 ms 62052 KB Output is correct
12 Correct 388 ms 62256 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 380 ms 62376 KB Output is correct
3 Correct 424 ms 62508 KB Output is correct
4 Correct 439 ms 62716 KB Output is correct
5 Correct 426 ms 62556 KB Output is correct
6 Correct 383 ms 62568 KB Output is correct
7 Correct 389 ms 62760 KB Output is correct
8 Correct 69 ms 63080 KB Output is correct
9 Correct 69 ms 62920 KB Output is correct
10 Correct 414 ms 62920 KB Output is correct
11 Incorrect 297 ms 62780 KB Output isn't correct
12 Halted 0 ms 0 KB -