oj.uz

Submission #669830

# Submission time Handle Problem Language Result Execution time Memory
669830 2022-12-07T12:07:56 Z Darren0724 Railway Trip 2 (JOI22_ho_t4) C++17
36 / 100
 1994 ms 392096 KB 
//challenge: 100
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define x first
#define y second
#define endl '\n'
int n,k,m;
const int INF=1e9;
vector<vector<int>> dp1,dp2;
struct segmax{
    int l,r,m;
    int val=-INF;
    int lz=-INF;
    segmax *lc,*rc;
    segmax(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new segmax(l,m);
        rc=new segmax(m,r);
    }
    int rv(){
        if(lz==-INF){
            return val;
        }
        return max(val,lz);
    }
    void pull(){
        val=max({lc->rv(),rc->rv(),val});
    }
    void push(){
        if(lz!=-INF){
            lc->lz=max(lc->lz,lz);
            rc->lz=max(rc->lz,lz);
            lz=-INF;
        }
        pull();
    }
    void add(int a,int b,int x){
        if(a<=l&&b>=r){
            lz=max(lz,x);
            return;
        }
        push();
        if(a<m){
            lc->add(a,b,x);
        }
        if(b>m){
            rc->add(a,b,x);
        }
        pull();
    }
    int query(int a,int b){
        if(a<=l&&b>=r){
            return rv();
        }
        push();
        int ans=-INF;
        if(a<m){
            ans=max(ans,lc->query(a,b));
        }
        if(b>m){
            ans=max(ans,rc->query(a,b));
        }
        pull();
        return ans;
    }
};
struct segmin{
    int l,r,m;
    int val=INF;
    int lz=INF;
    segmin *lc,*rc;
    segmin(int l1,int r1){
        l=l1,r=r1;
        m=(l+r)>>1;
        if(r-l==1){
            return;
        }
        lc=new segmin(l,m);
        rc=new segmin(m,r);
    }
    int rv(){
        if(lz==INF){
            return val;
        }
        return min(val,lz);
    }
    void pull(){
        val=min({lc->rv(),rc->rv(),val});
    }
    void push(){
        if(lz!=INF){
            lc->lz=min(lc->lz,lz);
            rc->lz=min(rc->lz,lz);
            lz=INF;
        }
        pull();
    }
    void add(int a,int b,int x){
        if(a<=l&&b>=r){
            lz=min(lz,x);
            return;
        }
        push();
        if(a<m){
            lc->add(a,b,x);
        }
        if(b>m){
            rc->add(a,b,x);
        }
        pull();
    }
    int query(int a,int b){
        if(a<=l&&b>=r){
            return rv();
        }
        push();
        int ans=INF;
        if(a<m){
            ans=min(ans,lc->query(a,b));
        }
        if(b>m){
            ans=min(ans,rc->query(a,b));
        }
        pull();
        return ans;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k>>m;
    dp1.resize(20,vector<int>(n));
    dp2.resize(20,vector<int>(n));
    segmax *rt=new segmax(0,n);
    segmin *rt1=new segmin(0,n);
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a<b){
            int c=min(b-1,a+k-1);
            rt->add(a,c+1,b);
        }
        else{
            int c=max(b+1,a-k+1);
            rt1->add(c,a+1,b);
        }
    }
    for(int i=0;i<n;i++){
        rt->add(i,i+1,i);
        rt1->add(i,i+1,i);
    }
    for(int i=0;i<n;i++){
        dp1[0][i]=rt1->query(i,i+1);
        dp2[0][i]=rt->query(i,i+1);
    }
    for(int i=1;i<20;i++){
        segmax *mx=new segmax(0,n);
        segmin *mn=new segmin(0,n);
        for(int j=0;j<n;j++){
            mx->add(j,j+1,dp2[i-1][j]);
            mn->add(j,j+1,dp1[i-1][j]);
        }
        for(int j=0;j<n;j++){
            dp1[i][j]=mn->query(dp1[i-1][j],dp2[i-1][j]+1);
            dp2[i][j]=mx->query(dp1[i-1][j],dp2[i-1][j]+1);
        }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        if(a<b){
            if(dp2[19][a]<b){
                cout<<-1<<endl;
            }
            else{
                int ans=0;
                for(int j=19;j>=0;j--){
                    if(dp2[j][a]<b){
                        ans+=(1<<j);
                        a=dp2[j][a];
                    }
                }
                cout<<ans+1<<endl;
            }
        }
        else{
            if(dp1[19][a]>b){
                cout<<-1<<endl;
            }
            else{
                int ans=0;
                for(int j=19;j>=0;j--){
                    if(dp1[j][a]>b){
                        ans+=(1<<j);
                        a=dp1[j][a];
                    }
                }
                cout<<ans+1<<endl;
            }
        }
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1492 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 1950 ms 391676 KB Output is correct
2 Correct 1859 ms 391728 KB Output is correct
3 Correct 1951 ms 391660 KB Output is correct
4 Correct 1788 ms 391704 KB Output is correct
5 Correct 1186 ms 391764 KB Output is correct
6 Correct 1781 ms 391692 KB Output is correct
7 Correct 1097 ms 391744 KB Output is correct
8 Correct 1044 ms 387684 KB Output is correct
9 Correct 1058 ms 391676 KB Output is correct
10 Correct 1846 ms 391724 KB Output is correct
11 Correct 1652 ms 391792 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1728 ms 392076 KB Output is correct
2 Correct 1780 ms 391908 KB Output is correct
3 Correct 1994 ms 392096 KB Output is correct
4 Correct 1093 ms 391836 KB Output is correct
5 Correct 1151 ms 387820 KB Output is correct
6 Correct 1171 ms 391904 KB Output is correct
7 Correct 1927 ms 391840 KB Output is correct
8 Correct 1651 ms 391888 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1686 ms 391924 KB Output is correct
2 Correct 1816 ms 392048 KB Output is correct
3 Correct 1830 ms 392068 KB Output is correct
4 Correct 1940 ms 391876 KB Output is correct
5 Correct 1695 ms 391904 KB Output is correct
6 Correct 1963 ms 391888 KB Output is correct
7 Correct 1586 ms 391936 KB Output is correct
8 Correct 3 ms 1492 KB Output is correct
9 Correct 25 ms 8152 KB Output is correct
10 Correct 1672 ms 391612 KB Output is correct
11 Correct 1673 ms 391776 KB Output is correct
12 Correct 1640 ms 387856 KB Output is correct
13 Correct 1671 ms 391716 KB Output is correct
14 Incorrect 4 ms 1492 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -