Submission #1077169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077169		isaachew	Railway Trip (JOI17_railway_trip)	C++17	5 / 100	2069 ms	524292 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);
    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++){
        for(int j=0;j<bylevel[i].size();j++){
            bylevel_set[i][bylevel[i][j]]=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=(--bylevel_set[j].lower_bound(la))->first;
                int curt=bylevel_set[j-1][la];
                int nxtt=bylevel_set[j-1][nlev];
                lda+=std::abs(curt-nxtt);
                la=nlev;
            }
            if(levels[ra]<j){
                int nlev=bylevel_set[j].upper_bound(ra)->first;
                int curt=bylevel_set[j-1][ra];
                int nxtt=bylevel_set[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=(--bylevel_set[j].lower_bound(lb))->first;
                int curt=bylevel_set[j-1][lb];
                int nxtt=bylevel_set[j-1][nlev];
                ldb+=std::abs(curt-nxtt);
                lb=nlev;
            }
            if(levels[rb]<j){
                int nlev=bylevel_set[j].upper_bound(rb)->first;
                int curt=bylevel_set[j-1][rb];
                int nxtt=bylevel_set[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+bylevel_set[j][lb]-bylevel_set[j][ra]);
        }
        std::cout<<res-1<<'\n';
    }
}

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