oj.uz

Submission #1077169

# Submission time Handle Problem Language Result Execution time Memory
1077169 2024-08-27T02:23:06 Z isaachew Railway Trip (JOI17_railway_trip) C++17
5 / 100
 2000 ms 524292 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);
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 608 KB Output is correct
5 Correct 0 ms 452 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 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 59 ms 27728 KB Output is correct
2 Correct 85 ms 29152 KB Output is correct
3 Correct 155 ms 54612 KB Output is correct
4 Correct 400 ms 131544 KB Output is correct
5 Correct 774 ms 259516 KB Output is correct
6 Runtime error 1256 ms 524292 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1468 ms 40916 KB Output is correct
2 Correct 980 ms 30620 KB Output is correct
3 Correct 1575 ms 43540 KB Output is correct
4 Correct 1755 ms 46204 KB Output is correct
5 Correct 1848 ms 48568 KB Output is correct
6 Execution timed out 2069 ms 53636 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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