답안 #899779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899779 2024-01-07T01:30:22 Z MilosMilutinovic Railway Trip (JOI17_railway_trip) C++14
0 / 100
57 ms 68812 KB
#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[l][k], mn[r - (1 << k) + 1][k]);
    int y = max(mx[l][k], mx[r - (1 << k) + 1][k]);
    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]);
  }; 
  cout << "! " << L[0][5] << " " << R[0][5] << '\n';
  cout << QueryMin(1, 5, 5) << " " << QueryMax(1, 5, 5) << '\n';
  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;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 1284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 49 ms 68812 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 57 ms 68664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -