oj.uz

Submission #671520

# Submission time Handle Problem Language Result Execution time Memory
671520 2022-12-13T06:17:20 Z Darren0724 Railway Trip 2 (JOI22_ho_t4) C++17
25 / 100
 2000 ms 394832 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1930 ms 391756 KB Output is correct
2 Correct 1809 ms 391656 KB Output is correct
3 Execution timed out 2068 ms 391660 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1732 ms 392064 KB Output is correct
2 Correct 1780 ms 391912 KB Output is correct
3 Correct 1992 ms 392008 KB Output is correct
4 Correct 1110 ms 394324 KB Output is correct
5 Correct 1170 ms 390648 KB Output is correct
6 Correct 1175 ms 394552 KB Output is correct
7 Correct 1945 ms 394672 KB Output is correct
8 Correct 1652 ms 394832 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1703 ms 392032 KB Output is correct
2 Correct 1852 ms 391896 KB Output is correct
3 Correct 1796 ms 391980 KB Output is correct
4 Correct 1957 ms 391972 KB Output is correct
5 Correct 1713 ms 391996 KB Output is correct
6 Correct 1967 ms 391868 KB Output is correct
7 Correct 1587 ms 391724 KB Output is correct
8 Correct 4 ms 1492 KB Output is correct
9 Correct 29 ms 8104 KB Output is correct
10 Correct 1787 ms 391740 KB Output is correct
11 Correct 1967 ms 391788 KB Output is correct
12 Correct 1859 ms 387972 KB Output is correct
13 Correct 1727 ms 391904 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 -