oj.uz

Submission #827765

# Submission time Handle Problem Language Result Execution time Memory
827765 2023-08-16T17:50:35 Z winter0101 Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 1136 ms 284604 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
#define pli pair<long long,int>
const int maxn=1e5+9;
struct line{
int l,r;
}a[maxn*2];
pii b[maxn],jump[maxn][18];
int minl[maxn][18][18],maxr[maxn][18][18];
vector<int>add[maxn],del[maxn];
int lg[maxn];
int get1(int l,int r,int k){
int dis=lg[r-l+1];
return min(minl[l][dis][k],minl[r-(1<<dis)+1][dis][k]);
}
int get2(int l,int r,int k){
int dis=lg[r-l+1];
return max(maxr[l][dis][k],maxr[r-(1<<dis)+1][dis][k]);
}
bool checkinside(int l,int r,int x){
return (l<=x&&x<=r);
}
int n,k,m;
void buildleft(){
    for1(i,1,n)b[i]={i,i};
    for1(i,1,m){
    if (a[i].l>a[i].r){
        add[a[i].l].pb(a[i].r);
        del[max(a[i].l-k+1,a[i].r+1)].pb(a[i].r);
        //cerr<<a[i].l<<" "<<min(a[i].l-k+1,a[i].r+1)<<'\n';
    }
    }
    multiset<int>ss;
    for2(i,n,1){
    for (auto v:add[i]){
        ss.insert(v);
    }
    if (!ss.empty())b[i].fi=*ss.begin();
    for (auto v:del[i]){
        ss.erase(ss.find(v));
    }
    vector<int>().swap(add[i]);
    vector<int>().swap(del[i]);
    }
}
void buildright(){
    for1(i,1,m){
    if (a[i].l<a[i].r){
        add[a[i].l].pb(a[i].r);
        del[min(a[i].l+k-1,a[i].r-1)].pb(a[i].r);
    }
    }
    multiset<int>ss;
    for1(i,1,n){
    for (auto v:add[i]){
        ss.insert(v);
    }
    if (!ss.empty()){
        auto it=ss.end();
        it--;
        b[i].se=*it;
    }
    for (auto v:del[i]){
        ss.erase(ss.find(v));
    }
    vector<int>().swap(add[i]);
    vector<int>().swap(del[i]);
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>k>>m;
    for1(i,2,n)lg[i]=lg[i/2]+1;
    for1(i,1,m){
    cin>>a[i].l>>a[i].r;
    }
    buildleft();
    buildright();
    //cout<<b[3].fi<<" "<<b[3].se<<'\n';
    //return 0;
    for1(i,1,n){
    jump[i][0]=b[i];
    }
    for1(j,1,18){
    for1(i,1,n){
    minl[i][0][j-1]=jump[i][j-1].fi;
    maxr[i][0][j-1]=jump[i][j-1].se;
    }
    for1(l,1,17){
    for1(i,1,n-(1<<l)+1){
    minl[i][l][j-1]=min(minl[i][l-1][j-1],minl[i+(1<<(l-1))][l-1][j-1]);
    maxr[i][l][j-1]=max(maxr[i][l-1][j-1],maxr[i+(1<<(l-1))][l-1][j-1]);
    }
    }
    if (j==18)break;
    for1(i,1,n){
    int l1=jump[i][j-1].fi,r1=jump[i][j-1].se;
    int newl1=min(l1,get1(l1,r1,j-1)),newr1=max(r1,get2(l1,r1,j-1));
    jump[i][j]={newl1,newr1};
    }
    }
    int q;
    cin>>q;
    for1(i,1,q){
    int s,t;
    cin>>s>>t;
    if (s==t){
        cout<<0<<'\n';
        continue;
    }
    int ans=0;
    pii nw={s,s};
    for2(j,17,0){
    int l1=nw.fi,r1=nw.se;
    int newl1=min(l1,get1(l1,r1,j)),newr1=max(r1,get2(l1,r1,j));
    //cerr<<j<<" "<<l1<<" "<<r1<<" "<<newl1<<" "<<newr1<<'\n';
    if (!checkinside(newl1,newr1,t)){
        //cerr<<j<<'\n';
        ans+=(1<<j);
        nw.fi=newl1;
        nw.se=newr1;
    }
    }
    //cout<<nw.fi<<" "<<nw.se<<'\n';
    for2(j,0,0){
    int l1=nw.fi,r1=nw.se;
    int newl1=min(l1,get1(l1,r1,j)),newr1=max(r1,get2(l1,r1,j));
    if (!checkinside(newl1,newr1,t)){
        cout<<-1<<'\n';
    }
    else cout<<ans+1<<'\n';
    }
    }
    //cout<<jump[3][1].fi<<" "<<jump[3][1].se<<'\n';

}

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5844 KB Output is correct
5 Correct 3 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 3 ms 5844 KB Output is correct
8 Correct 3 ms 5844 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 3 ms 5844 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 7 ms 10452 KB Output is correct
14 Correct 7 ms 10520 KB Output is correct
15 Correct 6 ms 10452 KB Output is correct
16 Correct 7 ms 10524 KB Output is correct
17 Correct 7 ms 10520 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Correct 8 ms 10256 KB Output is correct
20 Correct 7 ms 10452 KB Output is correct
21 Correct 6 ms 10452 KB Output is correct
22 Correct 7 ms 10528 KB Output is correct
23 Correct 7 ms 10500 KB Output is correct
24 Correct 7 ms 10440 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 277672 KB Output is correct
2 Correct 884 ms 277660 KB Output is correct
3 Correct 993 ms 277784 KB Output is correct
4 Correct 892 ms 277692 KB Output is correct
5 Correct 985 ms 280028 KB Output is correct
6 Correct 910 ms 282236 KB Output is correct
7 Correct 934 ms 279236 KB Output is correct
8 Correct 925 ms 275680 KB Output is correct
9 Correct 916 ms 278328 KB Output is correct
10 Correct 996 ms 279860 KB Output is correct
11 Correct 925 ms 279940 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 928 ms 279028 KB Output is correct
2 Correct 1000 ms 280520 KB Output is correct
3 Correct 935 ms 278580 KB Output is correct
4 Correct 977 ms 279320 KB Output is correct
5 Correct 931 ms 278552 KB Output is correct
6 Correct 942 ms 281376 KB Output is correct
7 Correct 943 ms 280104 KB Output is correct
8 Correct 960 ms 280296 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 282972 KB Output is correct
2 Correct 961 ms 281744 KB Output is correct
3 Correct 944 ms 278260 KB Output is correct
4 Correct 965 ms 275984 KB Output is correct
5 Correct 929 ms 275064 KB Output is correct
6 Correct 905 ms 274636 KB Output is correct
7 Correct 945 ms 280956 KB Output is correct
8 Correct 3 ms 5804 KB Output is correct
9 Correct 7 ms 10580 KB Output is correct
10 Correct 981 ms 283872 KB Output is correct
11 Correct 1136 ms 284604 KB Output is correct
12 Correct 993 ms 280936 KB Output is correct
13 Correct 986 ms 284544 KB Output is correct
14 Correct 3 ms 5796 KB Output is correct
15 Correct 7 ms 10552 KB Output is correct
16 Correct 950 ms 281788 KB Output is correct
17 Correct 960 ms 281844 KB Output is correct
18 Correct 970 ms 281860 KB Output is correct
19 Correct 969 ms 281712 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5844 KB Output is correct
2 Correct 3 ms 5844 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5844 KB Output is correct
5 Correct 3 ms 5844 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 3 ms 5844 KB Output is correct
8 Correct 3 ms 5844 KB Output is correct
9 Correct 3 ms 5844 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 3 ms 5844 KB Output is correct
12 Correct 3 ms 5844 KB Output is correct
13 Correct 7 ms 10452 KB Output is correct
14 Correct 7 ms 10520 KB Output is correct
15 Correct 6 ms 10452 KB Output is correct
16 Correct 7 ms 10524 KB Output is correct
17 Correct 7 ms 10520 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Correct 8 ms 10256 KB Output is correct
20 Correct 7 ms 10452 KB Output is correct
21 Correct 6 ms 10452 KB Output is correct
22 Correct 7 ms 10528 KB Output is correct
23 Correct 7 ms 10500 KB Output is correct
24 Correct 7 ms 10440 KB Output is correct
25 Correct 969 ms 277672 KB Output is correct
26 Correct 884 ms 277660 KB Output is correct
27 Correct 993 ms 277784 KB Output is correct
28 Correct 892 ms 277692 KB Output is correct
29 Correct 985 ms 280028 KB Output is correct
30 Correct 910 ms 282236 KB Output is correct
31 Correct 934 ms 279236 KB Output is correct
32 Correct 925 ms 275680 KB Output is correct
33 Correct 916 ms 278328 KB Output is correct
34 Correct 996 ms 279860 KB Output is correct
35 Correct 925 ms 279940 KB Output is correct
36 Correct 928 ms 279028 KB Output is correct
37 Correct 1000 ms 280520 KB Output is correct
38 Correct 935 ms 278580 KB Output is correct
39 Correct 977 ms 279320 KB Output is correct
40 Correct 931 ms 278552 KB Output is correct
41 Correct 942 ms 281376 KB Output is correct
42 Correct 943 ms 280104 KB Output is correct
43 Correct 960 ms 280296 KB Output is correct
44 Correct 1014 ms 282972 KB Output is correct
45 Correct 961 ms 281744 KB Output is correct
46 Correct 944 ms 278260 KB Output is correct
47 Correct 965 ms 275984 KB Output is correct
48 Correct 929 ms 275064 KB Output is correct
49 Correct 905 ms 274636 KB Output is correct
50 Correct 945 ms 280956 KB Output is correct
51 Correct 3 ms 5804 KB Output is correct
52 Correct 7 ms 10580 KB Output is correct
53 Correct 981 ms 283872 KB Output is correct
54 Correct 1136 ms 284604 KB Output is correct
55 Correct 993 ms 280936 KB Output is correct
56 Correct 986 ms 284544 KB Output is correct
57 Correct 3 ms 5796 KB Output is correct
58 Correct 7 ms 10552 KB Output is correct
59 Correct 950 ms 281788 KB Output is correct
60 Correct 960 ms 281844 KB Output is correct
61 Correct 970 ms 281860 KB Output is correct
62 Correct 969 ms 281712 KB Output is correct
63 Correct 966 ms 278320 KB Output is correct
64 Correct 957 ms 278484 KB Output is correct
65 Correct 984 ms 278348 KB Output is correct
66 Correct 959 ms 280780 KB Output is correct
67 Correct 959 ms 282444 KB Output is correct
68 Correct 946 ms 277568 KB Output is correct
69 Correct 982 ms 281292 KB Output is correct
70 Correct 935 ms 280164 KB Output is correct
71 Correct 969 ms 280176 KB Output is correct