oj.uz

Submission #887760

# Submission time Handle Problem Language Result Execution time Memory
887760 2023-12-15T07:39:35 Z owoovo Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 1485 ms 136300 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};
int fl[100010][20],fr[100010][20],n,m,k;
struct node{
    pair<int,int> val,tag;
};
struct seg{
    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);
        }
    }
}tree[20];

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;
    }
    tree[0].build(1,n,0,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        if(a<b){
            tree[0].modify(1,n,a,min(a+k-1,b),0,b);
        }else{
            tree[0].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=tree[i-1].query(1,n,fl[j][i-1],fr[j][i-1],0);
            fl[j][i]=now.F;
            fr[j][i]=now.S;
        }
        tree[i].build(1,n,0,i);
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int s,t,ans=0;
        cin>>s>>t;
        pair<int,int> now={s,s};
        if(s<t){
            if(fr[s][18]<t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(tree[j].query(1,n,now.F,now.S,0).S<t){
                    ans+=1<<(j-1);
                    now=tree[j].query(1,n,now.F,now.S,0);
                }
            }
            cout<<ans+1<<"\n";
        }else{
            if(fl[s][18]>t){
                cout<<"-1\n";
                continue;
            }
            for(int j=18;j>0;j--){
                if(tree[j].query(1,n,now.F,now.S,0).F>t){
                    ans+=1<<(j-1);
                    now=tree[j].query(1,n,now.F,now.S,0);
                }
            }
            cout<<ans+1<<"\n";
        }
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41308 KB Output is correct
2 Correct 6 ms 41484 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 5 ms 41308 KB Output is correct
5 Correct 7 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 6 ms 41308 KB Output is correct
8 Correct 6 ms 41308 KB Output is correct
9 Correct 6 ms 41308 KB Output is correct
10 Correct 4 ms 41308 KB Output is correct
11 Correct 5 ms 41308 KB Output is correct
12 Correct 6 ms 41304 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41308 KB Output is correct
2 Correct 6 ms 41484 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 5 ms 41308 KB Output is correct
5 Correct 7 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 6 ms 41308 KB Output is correct
8 Correct 6 ms 41308 KB Output is correct
9 Correct 6 ms 41308 KB Output is correct
10 Correct 4 ms 41308 KB Output is correct
11 Correct 5 ms 41308 KB Output is correct
12 Correct 6 ms 41304 KB Output is correct
13 Correct 20 ms 43608 KB Output is correct
14 Correct 18 ms 43608 KB Output is correct
15 Correct 11 ms 43612 KB Output is correct
16 Correct 11 ms 43612 KB Output is correct
17 Correct 18 ms 43620 KB Output is correct
18 Correct 11 ms 43612 KB Output is correct
19 Correct 17 ms 43608 KB Output is correct
20 Correct 12 ms 43612 KB Output is correct
21 Correct 8 ms 43612 KB Output is correct
22 Correct 18 ms 43612 KB Output is correct
23 Correct 20 ms 43612 KB Output is correct
24 Correct 18 ms 43612 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 133088 KB Output is correct
2 Correct 654 ms 132944 KB Output is correct
3 Correct 788 ms 133000 KB Output is correct
4 Correct 642 ms 133472 KB Output is correct
5 Correct 327 ms 132912 KB Output is correct
6 Correct 652 ms 133100 KB Output is correct
7 Correct 216 ms 132948 KB Output is correct
8 Correct 212 ms 132856 KB Output is correct
9 Correct 208 ms 132948 KB Output is correct
10 Correct 721 ms 133204 KB Output is correct
11 Correct 574 ms 132920 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 133372 KB Output is correct
2 Correct 841 ms 133168 KB Output is correct
3 Correct 1401 ms 133204 KB Output is correct
4 Correct 412 ms 133200 KB Output is correct
5 Correct 490 ms 132944 KB Output is correct
6 Correct 484 ms 133204 KB Output is correct
7 Correct 1039 ms 133312 KB Output is correct
8 Correct 975 ms 133252 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 706 ms 133172 KB Output is correct
2 Correct 1485 ms 133432 KB Output is correct
3 Correct 1388 ms 133464 KB Output is correct
4 Correct 1332 ms 133380 KB Output is correct
5 Correct 958 ms 133256 KB Output is correct
6 Correct 1155 ms 133292 KB Output is correct
7 Correct 711 ms 133340 KB Output is correct
8 Correct 6 ms 41304 KB Output is correct
9 Correct 16 ms 43616 KB Output is correct
10 Correct 696 ms 132932 KB Output is correct
11 Correct 850 ms 133316 KB Output is correct
12 Correct 861 ms 133124 KB Output is correct
13 Correct 876 ms 133204 KB Output is correct
14 Correct 6 ms 41304 KB Output is correct
15 Correct 20 ms 43608 KB Output is correct
16 Correct 710 ms 135620 KB Output is correct
17 Correct 1351 ms 135968 KB Output is correct
18 Correct 1255 ms 136300 KB Output is correct
19 Correct 1203 ms 136108 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 41308 KB Output is correct
2 Correct 6 ms 41484 KB Output is correct
3 Correct 6 ms 41308 KB Output is correct
4 Correct 5 ms 41308 KB Output is correct
5 Correct 7 ms 41308 KB Output is correct
6 Correct 5 ms 41308 KB Output is correct
7 Correct 6 ms 41308 KB Output is correct
8 Correct 6 ms 41308 KB Output is correct
9 Correct 6 ms 41308 KB Output is correct
10 Correct 4 ms 41308 KB Output is correct
11 Correct 5 ms 41308 KB Output is correct
12 Correct 6 ms 41304 KB Output is correct
13 Correct 20 ms 43608 KB Output is correct
14 Correct 18 ms 43608 KB Output is correct
15 Correct 11 ms 43612 KB Output is correct
16 Correct 11 ms 43612 KB Output is correct
17 Correct 18 ms 43620 KB Output is correct
18 Correct 11 ms 43612 KB Output is correct
19 Correct 17 ms 43608 KB Output is correct
20 Correct 12 ms 43612 KB Output is correct
21 Correct 8 ms 43612 KB Output is correct
22 Correct 18 ms 43612 KB Output is correct
23 Correct 20 ms 43612 KB Output is correct
24 Correct 18 ms 43612 KB Output is correct
25 Correct 717 ms 133088 KB Output is correct
26 Correct 654 ms 132944 KB Output is correct
27 Correct 788 ms 133000 KB Output is correct
28 Correct 642 ms 133472 KB Output is correct
29 Correct 327 ms 132912 KB Output is correct
30 Correct 652 ms 133100 KB Output is correct
31 Correct 216 ms 132948 KB Output is correct
32 Correct 212 ms 132856 KB Output is correct
33 Correct 208 ms 132948 KB Output is correct
34 Correct 721 ms 133204 KB Output is correct
35 Correct 574 ms 132920 KB Output is correct
36 Correct 939 ms 133372 KB Output is correct
37 Correct 841 ms 133168 KB Output is correct
38 Correct 1401 ms 133204 KB Output is correct
39 Correct 412 ms 133200 KB Output is correct
40 Correct 490 ms 132944 KB Output is correct
41 Correct 484 ms 133204 KB Output is correct
42 Correct 1039 ms 133312 KB Output is correct
43 Correct 975 ms 133252 KB Output is correct
44 Correct 706 ms 133172 KB Output is correct
45 Correct 1485 ms 133432 KB Output is correct
46 Correct 1388 ms 133464 KB Output is correct
47 Correct 1332 ms 133380 KB Output is correct
48 Correct 958 ms 133256 KB Output is correct
49 Correct 1155 ms 133292 KB Output is correct
50 Correct 711 ms 133340 KB Output is correct
51 Correct 6 ms 41304 KB Output is correct
52 Correct 16 ms 43616 KB Output is correct
53 Correct 696 ms 132932 KB Output is correct
54 Correct 850 ms 133316 KB Output is correct
55 Correct 861 ms 133124 KB Output is correct
56 Correct 876 ms 133204 KB Output is correct
57 Correct 6 ms 41304 KB Output is correct
58 Correct 20 ms 43608 KB Output is correct
59 Correct 710 ms 135620 KB Output is correct
60 Correct 1351 ms 135968 KB Output is correct
61 Correct 1255 ms 136300 KB Output is correct
62 Correct 1203 ms 136108 KB Output is correct
63 Correct 1076 ms 134728 KB Output is correct
64 Correct 1426 ms 135040 KB Output is correct
65 Correct 1124 ms 134800 KB Output is correct
66 Correct 347 ms 135988 KB Output is correct
67 Correct 1096 ms 136192 KB Output is correct
68 Correct 1087 ms 135740 KB Output is correct
69 Correct 515 ms 136144 KB Output is correct
70 Correct 864 ms 136092 KB Output is correct
71 Correct 1307 ms 136016 KB Output is correct