oj.uz

Submission #1077176

# Submission time Handle Problem Language Result Execution time Memory
1077176 2024-08-27T02:32:25 Z isaachew Railway Trip (JOI17_railway_trip) C++17
30 / 100
 220 ms 524288 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15196 KB Output is correct
2 Correct 17 ms 16340 KB Output is correct
3 Correct 31 ms 30544 KB Output is correct
4 Correct 72 ms 73316 KB Output is correct
5 Correct 136 ms 144068 KB Output is correct
6 Runtime error 212 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 23344 KB Output is correct
2 Correct 61 ms 17868 KB Output is correct
3 Correct 76 ms 25032 KB Output is correct
4 Correct 83 ms 26312 KB Output is correct
5 Correct 75 ms 27844 KB Output is correct
6 Correct 92 ms 30408 KB Output is correct
7 Correct 103 ms 31948 KB Output is correct
8 Correct 26 ms 6344 KB Output is correct
9 Correct 38 ms 21444 KB Output is correct
10 Correct 48 ms 27532 KB Output is correct
11 Correct 52 ms 27432 KB Output is correct
12 Correct 51 ms 27364 KB Output is correct
13 Correct 49 ms 27380 KB Output is correct
14 Correct 51 ms 26824 KB Output is correct
15 Correct 74 ms 27084 KB Output is correct
16 Correct 86 ms 28868 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -