Submission #899753

#	Time	Username	Problem	Language	Result	Execution time	Memory
899753		MilosMilutinovic	Railway Trip (JOI17_railway_trip)	C++14	20 / 100	2057 ms	10108 KiB

railway_trip

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<vector<int>> g(n);
  vector<int> stk;
  for (int i = 0; i < n; i++) {
    while (!stk.empty() && a[stk.back()] < a[i]) {
      stk.pop_back();
    }
    if (!stk.empty()) {
      g[i].push_back(stk.back());
      g[stk.back()].push_back(i);
    }
    stk.push_back(i);
  }
  for (int i = n - 1; i >= 0; i--) {
    while (!stk.empty() && a[stk.back()] < a[i]) {
      stk.pop_back();
    }
    if (!stk.empty()) {
      g[i].push_back(stk.back());
      g[stk.back()].push_back(i);
    }
    stk.push_back(i);
  }
  while (q--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    vector<int> dist(n, -1);
    vector<int> que(1, a);
    dist[a] = 0;
    for (int b = 0; b < (int) que.size(); b++) {
      int x = que[b];
      for (int y : g[x]) {
        if (dist[y] == -1) {
          dist[y] = dist[x] + 1;
          que.push_back(y);
        }
      }
    }
    cout << dist[b] - 1 << '\n';
  }
  return 0;
}

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