Submission #1077238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077238		kwongweng	Railway Trip (JOI17_railway_trip)	C++17	20 / 100	2102 ms	10728 KiB

railway_trip

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=a; i>=b; i--)
#define pb push_back
#define fi first
#define se second

// find min k so that if I change k intervals to -1, I can add +-c[i]

int main(){
    ios::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);
    int n,k,q; cin>>n>>k>>q;
    vi a(n); FOR(i,0,n) cin>>a[i];
    vi l(n), r(n);
    vi g[n];
    stack<int> s;
    s.push(0);
    FOR(i,1,n){
        while (a[s.top()] < a[i]) s.pop();
        l[i] = s.top(); s.push(i);
        g[l[i]].pb(i); g[i].pb(l[i]);
    }
    while (!s.empty()) s.pop();
    s.push(n-1);
    ROF(i,n-2,0){
        while (a[s.top()] < a[i]) s.pop();
        r[i] = s.top(); s.push(i);
        g[r[i]].pb(i);
        g[i].pb(r[i]);
    }
    vi dist;
    FOR(i,0,q){
        int a, b; cin>>a>>b;
        a--; b--;
        dist.assign(n,-1);
        vi bfs; bfs.pb(a); dist[a]=0;
        FOR(j,0,bfs.size()){
            int u = bfs[j];
            for (int v : g[u]){
                if (dist[v]!=-1) continue;
                dist[v] = dist[u]+1; bfs.pb(v);
            }
        }
        cout<<dist[b]-1<<"\n"; 
    }
    return 0;
}

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