oj.uz

Submission #669827

# Submission time Handle Problem Language Result Execution time Memory
669827 2022-12-07T11:43:01 Z Darren0724 Railway Trip 2 (JOI22_ho_t4) C++17
36 / 100
 1666 ms 394784 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());
    }
    void push(){
        if(lz!=-INF){
            lc->lz=max(lc->lz,lz);
            rc->lz=max(rc->lz,lz);
            lz=-INF;
        }
    }
    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());
    }
    void push(){
        if(lz!=INF){
            lc->lz=min(lc->lz,lz);
            rc->lz=min(rc->lz,lz);
            lz=INF;
        }
    }
    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,a+k-1);
            rt->add(a,c+1,b);
        }
        else{
            int c=max(b,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 3 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 3 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 1645 ms 392668 KB Output is correct
2 Correct 1534 ms 392732 KB Output is correct
3 Correct 1653 ms 392912 KB Output is correct
4 Correct 1532 ms 392636 KB Output is correct
5 Correct 981 ms 394044 KB Output is correct
6 Correct 1507 ms 394088 KB Output is correct
7 Correct 870 ms 393712 KB Output is correct
8 Correct 853 ms 388864 KB Output is correct
9 Correct 868 ms 392768 KB Output is correct
10 Correct 1527 ms 394180 KB Output is correct
11 Correct 1375 ms 394068 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 393348 KB Output is correct
2 Correct 1499 ms 394684 KB Output is correct
3 Correct 1666 ms 393700 KB Output is correct
4 Correct 878 ms 394340 KB Output is correct
5 Correct 969 ms 390640 KB Output is correct
6 Correct 984 ms 394708 KB Output is correct
7 Correct 1589 ms 394784 KB Output is correct
8 Correct 1375 ms 394688 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1419 ms 394668 KB Output is correct
2 Correct 1520 ms 393808 KB Output is correct
3 Correct 1515 ms 393052 KB Output is correct
4 Correct 1615 ms 392772 KB Output is correct
5 Correct 1423 ms 392516 KB Output is correct
6 Correct 1641 ms 392492 KB Output is correct
7 Correct 1306 ms 393624 KB Output is correct
8 Correct 3 ms 1472 KB Output is correct
9 Correct 23 ms 8148 KB Output is correct
10 Correct 1446 ms 393976 KB Output is correct
11 Correct 1434 ms 394560 KB Output is correct
12 Correct 1407 ms 390640 KB Output is correct
13 Correct 1442 ms 394708 KB Output is correct
14 Incorrect 3 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 3 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -