oj.uz

Submission #887758

# Submission time Handle Problem Language Result Execution time Memory
887758 2023-12-15T07:32:07 Z owoovo Railway Trip 2 (JOI22_ho_t4) C++14
36 / 100
 994 ms 22616 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 MP(min(a.F,b.F),max(a.S,b.S));
}
pair<int,int> iit={maxn,0};
struct node{
    pair<int,int> val,tag;
};
int fl[100010][20],fr[100010][20],n,m,k;
node tri[400010];
void push(int l,int r,int id){ 
    if(tri[id].tag!=iit){
        tri[id].val=tri[id].tag+tri[id].val;
        if(l!=r){
            tri[lc].tag=tri[lc].tag+tri[id].tag;
            tri[rc].tag=tri[rc].tag+tri[id].tag;
        }
        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;
    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].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 4444 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 4444 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 811 ms 22608 KB Output is correct
2 Correct 734 ms 22364 KB Output is correct
3 Correct 889 ms 22608 KB Output is correct
4 Correct 689 ms 22360 KB Output is correct
5 Correct 351 ms 22364 KB Output is correct
6 Correct 737 ms 22364 KB Output is correct
7 Correct 236 ms 22360 KB Output is correct
8 Correct 214 ms 22108 KB Output is correct
9 Correct 231 ms 22608 KB Output is correct
10 Correct 823 ms 22360 KB Output is correct
11 Correct 650 ms 22364 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 22608 KB Output is correct
2 Correct 994 ms 22364 KB Output is correct
3 Correct 857 ms 22604 KB Output is correct
4 Correct 259 ms 22360 KB Output is correct
5 Correct 396 ms 22276 KB Output is correct
6 Correct 428 ms 22364 KB Output is correct
7 Correct 937 ms 22360 KB Output is correct
8 Correct 696 ms 22364 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 891 ms 22600 KB Output is correct
2 Correct 777 ms 22612 KB Output is correct
3 Correct 774 ms 22608 KB Output is correct
4 Correct 816 ms 22616 KB Output is correct
5 Correct 609 ms 22452 KB Output is correct
6 Correct 903 ms 22364 KB Output is correct
7 Correct 645 ms 22364 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 11 ms 6492 KB Output is correct
10 Correct 864 ms 22352 KB Output is correct
11 Correct 849 ms 22364 KB Output is correct
12 Correct 858 ms 22276 KB Output is correct
13 Correct 837 ms 22376 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 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -