oj.uz

답안 #669828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669828 2022-12-07T11:46:42 Z Darren0724 Railway Trip 2 (JOI22_ho_t4) C++17
36 / 100
 1719 ms 392208 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-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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1621 ms 391612 KB Output is correct
2 Correct 1507 ms 391656 KB Output is correct
3 Correct 1626 ms 391788 KB Output is correct
4 Correct 1491 ms 391684 KB Output is correct
5 Correct 997 ms 391644 KB Output is correct
6 Correct 1502 ms 391664 KB Output is correct
7 Correct 899 ms 391660 KB Output is correct
8 Correct 854 ms 387712 KB Output is correct
9 Correct 872 ms 391648 KB Output is correct
10 Correct 1536 ms 391776 KB Output is correct
11 Correct 1380 ms 391680 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1430 ms 392008 KB Output is correct
2 Correct 1475 ms 391812 KB Output is correct
3 Correct 1719 ms 392024 KB Output is correct
4 Correct 928 ms 391808 KB Output is correct
5 Correct 984 ms 387848 KB Output is correct
6 Correct 985 ms 391760 KB Output is correct
7 Correct 1584 ms 391888 KB Output is correct
8 Correct 1370 ms 391904 KB Output is correct

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1426 ms 391952 KB Output is correct
2 Correct 1516 ms 392208 KB Output is correct
3 Correct 1497 ms 392104 KB Output is correct
4 Correct 1583 ms 391992 KB Output is correct
5 Correct 1416 ms 391848 KB Output is correct
6 Correct 1616 ms 391952 KB Output is correct
7 Correct 1312 ms 391772 KB Output is correct
8 Correct 3 ms 1364 KB Output is correct
9 Correct 21 ms 8144 KB Output is correct
10 Correct 1411 ms 391736 KB Output is correct
11 Correct 1410 ms 391832 KB Output is correct
12 Correct 1411 ms 387808 KB Output is correct
13 Correct 1410 ms 391828 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -