Submission #899781

#	Time	Username	Problem	Language	Result	Execution time	Memory
899781		MilosMilutinovic	Railway Trip (JOI17_railway_trip)	C++14	100 / 100	1568 ms	501908 KiB

railway_trip

#include <bits/stdc++.h>

using namespace std;

struct rmq {
  const int L = 20;
  vector<vector<int>> mn;
  vector<vector<int>> mx;
  vector<int> logs;
  void build(vector<int> a) {
    int n = (int) a.size();
    mn.resize(L);
    mx.resize(L);
    mn[0] = a;
    mx[0] = a;
    logs.resize(n + 1);
    for (int i = 2; i <= n; i++) {
      logs[i] = logs[i >> 1] + 1;
    }
    for (int j = 1; j < L; j++) {
      mn[j].resize(n);
      mx[j].resize(n);
      for (int i = 0; i + (1 << j) <= n; i++) {
        mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
        mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
      }
    }
  }
  pair<int, int> query(int l, int r) {
    int k = logs[r - l + 1];
    int x = min(mn[k][l], mn[k][r - (1 << k) + 1]);
    int y = max(mx[k][l], mx[k][r - (1 << k) + 1]);
    return make_pair(x, y);
  }
};

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<int> prv(n);
  vector<int> stk;
  for (int i = 0; i < n; i++) {
    while (!stk.empty() && a[stk.back()] < a[i]) {
      stk.pop_back();
    }
    prv[i] = (stk.empty() ? i : stk.back());
    stk.push_back(i);
  }
  stk.clear();
  vector<int> nxt(n);
  for (int i = n - 1; i >= 0; i--) {
    while (!stk.empty() && a[stk.back()] < a[i]) {
      stk.pop_back();
    }
    nxt[i] = (stk.empty() ? i : stk.back());
    stk.push_back(i);
  }
  vector<int> logs(n + 1);
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i >> 1] + 1;
  }
  const int LOG = 20;
  vector<vector<int>> L(LOG, vector<int>(n));
  vector<vector<int>> R(LOG, vector<int>(n));
  L[0] = prv;
  R[0] = nxt;
  for (int j = 1; j < LOG; j++) {
    rmq st;
    st.build(L[j - 1]);
    for (int i = 0; i < n; i++) {
      L[j][i] = st.query(L[j - 1][i], R[j - 1][i]).first;
    }
    st.build(R[j - 1]);
    for (int i = 0; i < n; i++) {
      R[j][i] = st.query(L[j - 1][i], R[j - 1][i]).second;
    }
  }
  vector<vector<vector<int>>> mn(LOG, vector<vector<int>>(n, vector<int>(LOG)));
  vector<vector<vector<int>>> mx(LOG, vector<vector<int>>(n, vector<int>(LOG)));
  for (int l = 0; l < LOG; l++) {
    for (int i = 0; i < n; i++) {
      mn[l][i][0] = L[l][i];
      mx[l][i][0] = R[l][i];
    }
    for (int j = 1; j < LOG; j++) {
      for (int i = 0; i + (1 << j) <= n; i++) {
        mn[l][i][j] = min(mn[l][i][j - 1], mn[l][i + (1 << (j - 1))][j - 1]);
        mx[l][i][j] = max(mx[l][i][j - 1], mx[l][i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  auto QueryMin = [&](int i, int l, int r) {
    int k = logs[r - l + 1];
    return min(mn[i][l][k], mn[i][r - (1 << k) + 1][k]);
  };
  auto QueryMax = [&](int i, int l, int r) {
    int k = logs[r - l + 1];
    return max(mx[i][l][k], mx[i][r - (1 << k) + 1][k]);
  }; 
  while (q--) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    if (a > b) {
      swap(a, b);
    }
    int res = 0;
    int from, to;
    {
      int l = a, r = a;
      for (int i = LOG - 1; i >= 0; i--) {
        if (QueryMin(i, l, r) <= b && b <= QueryMax(i, l, r)) {
          continue;
        }
        int new_l = QueryMin(i, l, r);
        int new_r = QueryMax(i, l, r);
        l = new_l;
        r = new_r;
        res += (1 << i);
      }
      from = l;
      to = r;
    }
    {
      int l = b, r = b;
      for (int i = LOG - 1; i >= 0; i--) {
        if (max(from, QueryMin(i, l, r)) <= min(to, QueryMax(i, l, r))) {
          continue;
        }
        int new_l = QueryMin(i, l, r);
        int new_r = QueryMax(i, l, r);
        l = new_l;
        r = new_r;
        res += (1 << i);
      }
    }
    cout << res << '\n';
  }
  return 0;
}

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