oj.uz

Submission #827764

# Submission time Handle Problem Language Result Execution time Memory
827764 2023-08-16T17:49:42 Z winter0101 Railway Trip 2 (JOI22_ho_t4) C++14
16 / 100
 927 ms 279460 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];
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 5804 KB Output is correct
2 Correct 4 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 4948 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 5804 KB Output is correct
2 Correct 4 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 4948 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 10536 KB Output is correct
15 Correct 6 ms 10424 KB Output is correct
16 Correct 8 ms 10452 KB Output is correct
17 Correct 8 ms 10452 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Correct 7 ms 10284 KB Output is correct
20 Correct 8 ms 10460 KB Output is correct
21 Correct 7 ms 10452 KB Output is correct
22 Correct 7 ms 10452 KB Output is correct
23 Correct 7 ms 10452 KB Output is correct
24 Correct 7 ms 10452 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 918 ms 278180 KB Output is correct
2 Correct 921 ms 278164 KB Output is correct
3 Correct 919 ms 278348 KB Output is correct
4 Correct 915 ms 278156 KB Output is correct
5 Runtime error 23 ms 12748 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 279460 KB Output is correct
2 Runtime error 23 ms 12596 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 12456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5804 KB Output is correct
2 Correct 4 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 4948 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 10536 KB Output is correct
15 Correct 6 ms 10424 KB Output is correct
16 Correct 8 ms 10452 KB Output is correct
17 Correct 8 ms 10452 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Correct 7 ms 10284 KB Output is correct
20 Correct 8 ms 10460 KB Output is correct
21 Correct 7 ms 10452 KB Output is correct
22 Correct 7 ms 10452 KB Output is correct
23 Correct 7 ms 10452 KB Output is correct
24 Correct 7 ms 10452 KB Output is correct
25 Correct 918 ms 278180 KB Output is correct
26 Correct 921 ms 278164 KB Output is correct
27 Correct 919 ms 278348 KB Output is correct
28 Correct 915 ms 278156 KB Output is correct
29 Runtime error 23 ms 12748 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -