oj.uz

Submission #792093

# Submission time Handle Problem Language Result Execution time Memory
792093 2023-07-24T15:02:06 Z peijar Railway Trip (JOI17_railway_trip) C++17
100 / 100
 299 ms 34696 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e5;
const int MAXP = 20;

int goleft[MAXP][MAXN], goright[MAXP][MAXN];
int N, K, Q;

pair<int, int> advance(int L, int R, int p) {
  int nL, nR;
  if (L != -1)
    nL = goleft[p][L];
  else
    nL = -1;
  if (R != N)
    nL = min(nL, goleft[p][R]);
  if (R != N)
    nR = goright[p][R];
  else
    nR = N;
  if (L != -1)
    nR = max(nR, goright[p][L]);
  return pair(nL, nR);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> N >> K >> Q;

  vector<int> level(N);
  for (int &x : level)
    cin >> x;

  for (int i = 0; i < N; ++i) {
    int j = i - 1;
    while (j >= 0 and level[j] < level[i])
      j = goleft[0][j];

    goleft[0][i] = j;
  }

  for (int i = N - 1; i >= 0; --i) {
    int j = i + 1;
    while (j < N and level[j] < level[i])
      j = goright[0][j];
    goright[0][i] = j;
  }

  for (int p = 0; p < MAXP - 1; ++p)
    for (int i = 0; i < N; ++i) {
      int L = goleft[p][i];
      int R = goright[p][i];
      if (L != -1)
        goleft[p + 1][i] = goleft[p][L];
      else
        goleft[p + 1][i] = -1;
      if (R != N)
        goleft[p + 1][i] = min(goleft[p + 1][i], goleft[p][R]);
      if (R != N)
        goright[p + 1][i] = goright[p][R];
      else
        goright[p + 1][i] = N;
      if (L != -1)
        goright[p + 1][i] = max(goright[p + 1][i], goright[p][L]);
    }

  while (Q--) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    if (A > B)
      swap(A, B);
    int sol = 0;
    int LA = A, RA = A;

    /*while (advance(LA, RA, 0).second <= B) {
      sol++;
      tie(LA, RA) = advance(LA, RA, 0);
    }
    int LB = B, RB = B;
    while (advance(LB, RB, 0).first >= RA) {
      sol++;
      tie(LB, RB) = advance(LB, RB, 0);
    }*/
    for (int p = MAXP - 1; p >= 0; --p)
      if (advance(LA, RA, p).second <= B) {
        sol += 1 << p;
        tie(LA, RA) = advance(LA, RA, p);
      }

    int LB = B, RB = B;
    for (int p = MAXP - 1; p >= 0; --p)
      if (advance(LB, RB, p).first >= RA) {
        sol += 1 << p;
        tie(LB, RB) = advance(LB, RB, p);
      }

    if (RA < LB)
      sol++;
    cout << sol - 1 << '\n';
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 21 ms 32596 KB Output is correct
3 Correct 22 ms 32596 KB Output is correct
4 Correct 20 ms 32708 KB Output is correct
5 Correct 21 ms 32704 KB Output is correct
6 Correct 21 ms 32732 KB Output is correct
7 Correct 23 ms 32936 KB Output is correct
8 Correct 23 ms 32596 KB Output is correct
9 Correct 23 ms 32984 KB Output is correct
10 Correct 21 ms 32708 KB Output is correct
11 Correct 24 ms 32948 KB Output is correct
12 Correct 23 ms 32952 KB Output is correct
13 Correct 22 ms 32856 KB Output is correct
14 Correct 22 ms 32980 KB Output is correct
15 Correct 23 ms 32972 KB Output is correct
16 Correct 22 ms 32860 KB Output is correct
17 Correct 23 ms 32912 KB Output is correct
18 Correct 31 ms 32980 KB Output is correct
19 Correct 22 ms 32984 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 32840 KB Output is correct
2 Correct 227 ms 34252 KB Output is correct
3 Correct 219 ms 34268 KB Output is correct
4 Correct 230 ms 34248 KB Output is correct
5 Correct 227 ms 34232 KB Output is correct
6 Correct 207 ms 34272 KB Output is correct
7 Correct 201 ms 34260 KB Output is correct
8 Correct 236 ms 34316 KB Output is correct
9 Correct 290 ms 34468 KB Output is correct
10 Correct 299 ms 34252 KB Output is correct
11 Correct 289 ms 34312 KB Output is correct
12 Correct 291 ms 34344 KB Output is correct
13 Correct 276 ms 34280 KB Output is correct
14 Correct 216 ms 34168 KB Output is correct
15 Correct 187 ms 34192 KB Output is correct
16 Correct 177 ms 34132 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 32628 KB Output is correct
2 Correct 155 ms 34336 KB Output is correct
3 Correct 172 ms 34428 KB Output is correct
4 Correct 157 ms 34360 KB Output is correct
5 Correct 286 ms 34332 KB Output is correct
6 Correct 237 ms 34596 KB Output is correct
7 Correct 209 ms 34696 KB Output is correct
8 Correct 219 ms 34484 KB Output is correct
9 Correct 215 ms 34648 KB Output is correct
10 Correct 229 ms 34584 KB Output is correct
11 Correct 225 ms 34580 KB Output is correct
12 Correct 245 ms 34640 KB Output is correct
13 Correct 241 ms 34596 KB Output is correct
14 Correct 237 ms 34640 KB Output is correct
15 Correct 244 ms 34608 KB Output is correct
16 Correct 257 ms 34580 KB Output is correct
17 Correct 191 ms 34672 KB Output is correct
18 Correct 191 ms 34652 KB Output is correct
19 Correct 204 ms 34604 KB Output is correct
20 Correct 170 ms 34504 KB Output is correct
21 Correct 184 ms 34468 KB Output is correct
22 Correct 154 ms 34384 KB Output is correct
23 Correct 178 ms 34388 KB Output is correct