Submission #1077176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077176		isaachew	Railway Trip (JOI17_railway_trip)	C++17	30 / 100	220 ms	524288 KiB

railway_trip

#include <bits/stdc++.h>
/*
 20p: just Dijkstra
 45p: keep left/right for each level (impossible to go past them)
 Cartesian tree-like
 
 Square root?
 */
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::vector<int> levels;
    int n,k,q;
    std::cin>>n>>k>>q;
    std::vector<std::vector<int>> bylevel(k);
    //std::vector<std::map<int,int>> bylevel_set(k);
    std::vector<std::vector<int>> llevel(k,std::vector<int>(n)),rlevel(k,std::vector<int>(n)),linds(k,std::vector<int>(n));
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        x--;
        levels.push_back(x);
        for(int k=0;k<=x;k++)bylevel[k].push_back(i);
    }
    for(int i=0;i<k;i++){
        int p=0;
        for(int j=0;j<bylevel[i].size();j++){
            linds[i][bylevel[i][j]]=j;
            for(;p<=bylevel[i][j];p++){
                rlevel[i][p]=bylevel[i][j];
            }
        }
        p=n-1;
        for(int j=bylevel[i].size();--j;){
            for(;p>=bylevel[i][j];p--){
                llevel[i][p]=bylevel[i][j];
            }
        }
    }
    for(int i=0;i<q;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        if(a>b)std::swap(a,b);
        int la=a,lda=0,ra=a,rda=0;
        int lb=b,ldb=0,rb=b,rdb=0;
        int res=1e9;
        for(int j=0;j<k;j++){
            if(levels[la]<j){
                int nlev=llevel[j][la];
                int curt=linds[j-1][la];
                int nxtt=linds[j-1][nlev];
                lda+=std::abs(curt-nxtt);
                la=nlev;
            }
            if(levels[ra]<j){
                int nlev=rlevel[j][ra];
                int curt=linds[j-1][ra];
                int nxtt=linds[j-1][nlev];
                rda+=std::abs(curt-nxtt);
                ra=nlev;
            }
            lda=std::min(rda+1,lda);rda=std::min(lda+1,rda);
            if(levels[lb]<j){
                int nlev=llevel[j][lb];
                int curt=linds[j-1][lb];
                int nxtt=linds[j-1][nlev];
                ldb+=std::abs(curt-nxtt);
                lb=nlev;
            }
            if(levels[rb]<j){
                int nlev=rlevel[j][rb];
                int curt=linds[j-1][rb];
                int nxtt=linds[j-1][nlev];
                rdb+=std::abs(curt-nxtt);
                rb=nlev;
            }
            ldb=std::min(rdb+1,ldb);rdb=std::min(ldb+1,rdb);
            res=std::min(res,ldb+rda+linds[j][lb]-linds[j][ra]);
        }
        std::cout<<res-1<<'\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55