oj.uz

답안 #887737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887737 2023-12-15T06:45:04 Z owoovo Railway Trip 2 (JOI22_ho_t4) C++17
36 / 100
 1010 ms 27216 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-1),0,b);
        }else{
            modify(1,n,max(a-k+1,b+1),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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 826 ms 24864 KB Output is correct
2 Correct 758 ms 24656 KB Output is correct
3 Correct 927 ms 25028 KB Output is correct
4 Correct 724 ms 24812 KB Output is correct
5 Correct 401 ms 26192 KB Output is correct
6 Correct 754 ms 26228 KB Output is correct
7 Correct 386 ms 25940 KB Output is correct
8 Correct 248 ms 25000 KB Output is correct
9 Correct 245 ms 25056 KB Output is correct
10 Correct 863 ms 26352 KB Output is correct
11 Correct 682 ms 26448 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 725 ms 25776 KB Output is correct
2 Correct 1010 ms 26728 KB Output is correct
3 Correct 874 ms 25820 KB Output is correct
4 Correct 400 ms 26448 KB Output is correct
5 Correct 409 ms 26708 KB Output is correct
6 Correct 418 ms 26964 KB Output is correct
7 Correct 889 ms 26848 KB Output is correct
8 Correct 674 ms 26704 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 835 ms 27216 KB Output is correct
2 Correct 712 ms 25820 KB Output is correct
3 Correct 698 ms 25180 KB Output is correct
4 Correct 804 ms 24708 KB Output is correct
5 Correct 595 ms 24684 KB Output is correct
6 Correct 876 ms 24480 KB Output is correct
7 Correct 691 ms 25568 KB Output is correct
8 Correct 2 ms 4444 KB Output is correct
9 Correct 10 ms 4680 KB Output is correct
10 Correct 838 ms 26220 KB Output is correct
11 Correct 847 ms 26872 KB Output is correct
12 Correct 844 ms 26708 KB Output is correct
13 Correct 857 ms 26964 KB Output is correct
14 Incorrect 2 ms 4440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -