oj.uz

Submission #1063351

# Submission time Handle Problem Language Result Execution time Memory
1063351 2024-08-17T17:07:59 Z Unforgettablepl Railway Trip (JOI17_railway_trip) C++17
30 / 100
 2000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k,q;
    cin >> n >> k >> q;
    vector<int> l(n+2);
    for(int i=1;i<=n;i++)cin>>l[i];
    l[0]=l[n+1]=k+1;
    vector pref(k+1,vector(n+1,0));
    for(int i=1;i<=k;i++) {
        for(int j=1;j<=n;j++) {
            pref[i][j]=pref[i][j-1];
            if(l[j]>=i)pref[i][j]++;
        }
    }
    vector nearest_left(k+1,vector<pair<int,int>>(n+1,{INF,0}));
    vector nearest_right(k+1,vector<pair<int,int>>(n+1,{INF,0}));
    vector<vector<int>> adj(n+1);
    stack<pair<int,int>> s;
    for(int i=1;i<=n;i++) {
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    while(!s.empty())s.pop();
    for(int i=n;i;i--){
        while(!s.empty() and s.top().first<l[i])s.pop();
        if(!s.empty()) {
            adj[s.top().second].emplace_back(i);
            adj[i].emplace_back(s.top().second);
        }
        s.emplace(l[i],i);
    }
    for(int i=1;i<=k;i++){
        {
            // nearest right calculation
            vector<bool> visited(n+1);
            priority_queue<tuple<int,int,int>> qu;
            for(int x=1;x<=n;x++)if(l[x]>=i)qu.emplace(0,x,x);
            while(!qu.empty()) {
                auto [dist,source,idx] = qu.top();qu.pop();dist=-dist;
                if(visited[idx])continue;
                visited[idx]=true;
                nearest_right[i][idx]={dist,source};
                for(int&x:adj[idx])if(!visited[x])qu.emplace(-dist-1,source,x);
            }
        }
        {
            // nearest left calculation
            vector<bool> visited(n+1);
            priority_queue<tuple<int,int,int>> qu;
            for(int x=1;x<=n;x++)if(l[x]>=i)qu.emplace(0,-x,x);
            while(!qu.empty()) {
                auto [dist,source,idx] = qu.top();qu.pop();dist=-dist;source=-source;
                if(visited[idx])continue;
                visited[idx]=true;
                nearest_left[i][idx]={dist,source};
                for(int&x:adj[idx])if(!visited[x])qu.emplace(-dist-1,-source,x);
            }
        }
    }
    for(int i=1;i<=q;i++) {
        int oa,ob;
        cin >> oa >> ob;
        if(ob<oa)swap(oa,ob);
        int ans = INF;
        for(int level=1;level<=k;level++) {
            if(nearest_left[level][ob].second<nearest_right[level][oa].second)break;
            int a = nearest_right[level][oa].second;
            int b = nearest_left[level][ob].second;
            int currdist = nearest_right[level][oa].first+nearest_left[level][ob].first;
            ans = min(ans,currdist+pref[level][b]-pref[level][a]-1);
        }
        cout << ans << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 4 ms 852 KB Output is correct
4 Correct 5 ms 712 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 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 472 ms 35932 KB Output is correct
2 Correct 661 ms 59700 KB Output is correct
3 Correct 1274 ms 95048 KB Output is correct
4 Execution timed out 2025 ms 200780 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 74016 KB Output is correct
2 Correct 700 ms 59888 KB Output is correct
3 Correct 1028 ms 77460 KB Output is correct
4 Correct 1119 ms 81056 KB Output is correct
5 Correct 1164 ms 84724 KB Output is correct
6 Correct 1323 ms 91752 KB Output is correct
7 Correct 1355 ms 95208 KB Output is correct
8 Correct 172 ms 32212 KB Output is correct
9 Correct 236 ms 77536 KB Output is correct
10 Correct 303 ms 95220 KB Output is correct
11 Correct 294 ms 95108 KB Output is correct
12 Correct 291 ms 95196 KB Output is correct
13 Correct 283 ms 95200 KB Output is correct
14 Correct 431 ms 93804 KB Output is correct
15 Correct 770 ms 93664 KB Output is correct
16 Correct 1095 ms 93924 KB Output is correct

Subtask #4
0 / 55.0

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