Submission #1046106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046106		juicy	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	67 ms	16756 KiB

railway_trip

// https://github.com/tmwilliamlin168/CompetitiveProgramming/blob/master/JOI/17S-Railway(2).cpp

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 17;

int n, k, q;
int a[N], L[LG][N], R[LG][N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  vector<int> st;
  for (int i = 1; i <= n; ++i) {
    while (st.size() && a[st.back()] < a[i]) {
      st.pop_back();
    }
    L[0][i] = st.size() ? st.back() : 1;
    st.push_back(i);
  }
  st.clear();
  for (int i = n; i > 0; --i) {
    while (st.size() && a[st.back()] < a[i]) {
      st.pop_back();
    }
    R[0][i] = st.size() ? st.back() : n;
    st.push_back(i);
  }
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      int u = L[j - 1][i], v = R[j - 1][i];
      L[j][i] = min(L[j - 1][u], L[j - 1][v]);
      R[j][i] = max(R[j - 1][u], R[j - 1][v]);
    }
  }
  while (q--) {
    int s, t; cin >> s >> t;
    if (s > t) {
      swap(s, t);
    }
    int l = s, r = s, res = 0, b = t;
    for (int j = LG - 1; ~j; --j) {
      if (max(R[j][l], R[j][r]) < b) {
        res += 1 << j;
        int u = l, v = r;
        l = min(L[j][u], L[j][v]);
        r = max(R[j][u], R[j][v]);
      }
    }
    b = r, l = t, r = t;
    for (int j = LG - 1; ~j; --j) {
      if (min(L[j][l], L[j][r]) > b) {
        res += 1 << j;
        int u = l, v = r;
        l = min(L[j][u], L[j][v]);
        r = max(R[j][u], R[j][v]);
      }
    }
    cout << res << "\n";
  }
  return 0;
}

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