oj.uz

Submission #899781

# Submission time Handle Problem Language Result Execution time Memory
899781 2024-01-07T01:32:51 Z MilosMilutinovic Railway Trip (JOI17_railway_trip) C++14
100 / 100
 1568 ms 501908 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[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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 1 ms 1112 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5372 KB Output is correct
2 Correct 932 ms 499348 KB Output is correct
3 Correct 899 ms 499476 KB Output is correct
4 Correct 883 ms 499504 KB Output is correct
5 Correct 886 ms 499416 KB Output is correct
6 Correct 853 ms 499724 KB Output is correct
7 Correct 874 ms 499772 KB Output is correct
8 Correct 875 ms 499860 KB Output is correct
9 Correct 893 ms 499608 KB Output is correct
10 Correct 858 ms 499736 KB Output is correct
11 Correct 897 ms 499780 KB Output is correct
12 Correct 868 ms 499784 KB Output is correct
13 Correct 859 ms 499788 KB Output is correct
14 Correct 874 ms 499908 KB Output is correct
15 Correct 891 ms 499852 KB Output is correct
16 Correct 897 ms 499776 KB Output is correct
17 Correct 868 ms 499648 KB Output is correct
18 Correct 850 ms 499764 KB Output is correct
19 Correct 857 ms 499676 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 500972 KB Output is correct
2 Correct 1401 ms 500916 KB Output is correct
3 Correct 1431 ms 501196 KB Output is correct
4 Correct 1384 ms 500944 KB Output is correct
5 Correct 1384 ms 501360 KB Output is correct
6 Correct 1382 ms 500924 KB Output is correct
7 Correct 1402 ms 501260 KB Output is correct
8 Correct 1442 ms 501468 KB Output is correct
9 Correct 1544 ms 501292 KB Output is correct
10 Correct 1548 ms 501344 KB Output is correct
11 Correct 1543 ms 501468 KB Output is correct
12 Correct 1542 ms 501652 KB Output is correct
13 Correct 1568 ms 501400 KB Output is correct
14 Correct 1414 ms 500960 KB Output is correct
15 Correct 1364 ms 500800 KB Output is correct
16 Correct 1373 ms 500948 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1213 ms 500652 KB Output is correct
2 Correct 1219 ms 500892 KB Output is correct
3 Correct 1249 ms 500892 KB Output is correct
4 Correct 1207 ms 501108 KB Output is correct
5 Correct 1566 ms 501832 KB Output is correct
6 Correct 1451 ms 501908 KB Output is correct
7 Correct 1449 ms 501504 KB Output is correct
8 Correct 1464 ms 501808 KB Output is correct
9 Correct 1395 ms 501516 KB Output is correct
10 Correct 1424 ms 501320 KB Output is correct
11 Correct 1421 ms 501676 KB Output is correct
12 Correct 1403 ms 501560 KB Output is correct
13 Correct 1423 ms 501864 KB Output is correct
14 Correct 1426 ms 501300 KB Output is correct
15 Correct 1449 ms 501440 KB Output is correct
16 Correct 1444 ms 501504 KB Output is correct
17 Correct 1336 ms 501360 KB Output is correct
18 Correct 1318 ms 501592 KB Output is correct
19 Correct 1342 ms 501472 KB Output is correct
20 Correct 1297 ms 501088 KB Output is correct
21 Correct 1179 ms 501180 KB Output is correct
22 Correct 1200 ms 501040 KB Output is correct
23 Correct 1186 ms 501140 KB Output is correct