oj.uz

Submission #887752

# Submission time Handle Problem Language Result Execution time Memory
887752 2023-12-15T07:21:34 Z owoovo Railway Trip 2 (JOI22_ho_t4) C++14
36 / 100
 835 ms 24404 KB 
#include<bits/stdc++.h>
#define F first 
#define S second
#define lc id*2+1
#define rc id*2+2
#define MP make_pair
using namespace std;
const int maxn=1e6;
pair<int,int> operator+(pair<int,int> a,pair<int,int> b){
    return {min(a.F,b.F),max(a.S,b.S)};
}
pair<int,int> iit={maxn,0};
struct node{
    pair<int,int> val,tag;
    int ist=0;
};
int fl[100010][20],fr[100010][20],n,m,k;
node tri[400010];
void push(int l,int r,int id){ 
    if(tri[id].ist){
        tri[id].val=tri[id].tag+tri[id].val;
        if(l!=r){
            tri[lc].ist=1;
            tri[rc].ist=1;
            tri[lc].tag=tri[lc].tag+tri[id].tag;
            tri[rc].tag=tri[rc].tag+tri[id].tag;
        }
        tri[id].ist=0;
        tri[id].tag=iit;
    }
    return;
}
void pull(int l,int r,int id){
    push(l,r,id);
    if(l!=r){
        int m=(l+r)>>1;
        push(l,m,lc);
        push(m+1,r,rc);
        tri[id].val=tri[lc].val+tri[rc].val;
    }
    return;
}
void build(int l,int r,int id,int i){
    tri[id].tag=iit;
    tri[id].ist=0;
    if(l==r){
        tri[id].val={fl[l][i],fr[l][i]};
        return;
    }
    int m=(l+r)>>1;
    build(l,m,lc,i);
    build(m+1,r,rc,i);
    pull(l,r,id);
}
void modify(int l,int r,int L,int R,int id,int x){
    pull(l,r,id);
    if(l==L&&r==R){
        tri[id].ist=1;
        tri[id].tag=tri[id].tag+MP(x,x);
        return;
    }
    int m=(l+r)>>1;
    if(R<=m){
        modify(l,m,L,R,lc,x);
    }else if(L>m){
        modify(m+1,r,L,R,rc,x);
    }else{
        modify(l,m,L,m,lc,x);
        modify(m+1,r,m+1,R,rc,x);
    }
    pull(l,r,id);
    return;
}
pair<int,int> query(int l,int r,int L,int R,int id){
    pull(l,r,id);
    if(l==L&&r==R){
        return tri[id].val;
    }
    int m=(l+r)>>1;
    if(R<=m){
        return query(l,m,L,R,lc);
    }else if(L>m){
        return query(m+1,r,L,R,rc);
    }else{
        return query(l,m,L,m,lc)+query(m+1,r,m+1,R,rc);
    }
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>k>>m;
    for(int j=1;j<=n;j++){
        fl[j][0]=j;
        fr[j][0]=j;
    }
    build(1,n,0,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(a<b){
            modify(1,n,a,min(a+k-1,b),0,b);
        }else{
            modify(1,n,max(a-k+1,b),a,0,b);
        }
    }
    for(int i=1;i<=18;i++){
        for(int j=1;j<=n;j++){
            auto now=query(1,n,fl[j][i-1],fr[j][i-1],0);
            fl[j][i]=now.F;
            fr[j][i]=now.S;
        }
        build(1,n,0,i);
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int s,t,ans=0;
        cin>>s>>t;
        if(s<t){
            if(fr[s][18]<t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(fr[s][j]<t){
                    ans+=1<<(j-1);
                    s=fr[s][j];
                }
            }
            cout<<ans+1<<"\n";
        }else{
            if(fl[s][18]>t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(fl[s][j]>t){
                    ans+=1<<(j-1);
                    s=fl[s][j];
                }
            }
            cout<<ans+1<<"\n";
        }
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 23920 KB Output is correct
2 Correct 575 ms 23916 KB Output is correct
3 Correct 697 ms 23916 KB Output is correct
4 Correct 558 ms 23896 KB Output is correct
5 Correct 352 ms 23920 KB Output is correct
6 Correct 562 ms 23920 KB Output is correct
7 Correct 224 ms 23896 KB Output is correct
8 Correct 213 ms 23864 KB Output is correct
9 Correct 217 ms 23896 KB Output is correct
10 Correct 659 ms 24144 KB Output is correct
11 Correct 507 ms 23920 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 23920 KB Output is correct
2 Correct 835 ms 24032 KB Output is correct
3 Correct 658 ms 24404 KB Output is correct
4 Correct 233 ms 23936 KB Output is correct
5 Correct 365 ms 23844 KB Output is correct
6 Correct 364 ms 23920 KB Output is correct
7 Correct 657 ms 23920 KB Output is correct
8 Correct 512 ms 23920 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 675 ms 23920 KB Output is correct
2 Correct 533 ms 24144 KB Output is correct
3 Correct 524 ms 24176 KB Output is correct
4 Correct 600 ms 24184 KB Output is correct
5 Correct 436 ms 23920 KB Output is correct
6 Correct 656 ms 23920 KB Output is correct
7 Correct 490 ms 23900 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 8 ms 4444 KB Output is correct
10 Correct 675 ms 23900 KB Output is correct
11 Correct 691 ms 23896 KB Output is correct
12 Correct 687 ms 23840 KB Output is correct
13 Correct 697 ms 23920 KB Output is correct
14 Incorrect 2 ms 4444 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -