oj.uz

Submission #980289

# Submission time Handle Problem Language Result Execution time Memory
980289 2024-05-12T02:57:36 Z Tsagana Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 688 ms 43512 KB 
#include "jumps.h"

//OP
#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pi pair<int, int >
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mset multiset
#define F first
#define S second
#define meta int M = (L + R) / 2, x = 2 * id + 1, y = x + 1

using namespace std;

bool one;
 
struct tree {
  int n;
  int lj[200005];
  int rj[200005];
  int jr[200005][20];
  int jl[200005][20];
  vector<int> h;
  pi t[800005];

  void build(int id, int L, int R) {
    if (L == R) {t[id] = {h[L], L}; return ;}
    meta;
    build(x, L, M);
    build(y, M + 1, R);
    t[id] = max(t[x], t[y]);
  } void build() {build(0, 0, n-1); return ;}
 
  pi query(int id, int L, int R, int l, int r) {
    if (R <  l || r <  L) return {-2e9, -1};
    if (l <= L && r >= R) return t[id];
    meta;
    return max(query(x, L, M, l, r), query(y, M + 1, R, l, r));
  } pi query(int L, int R) {return query(0, 0, n-1, L, R);}

  void take_J(vector<int> H) {
    stack<int> st;
    for (int i = 0; i < n; i++) {
      while (!st.empty() && H[st.top()] < H[i]) st.pop();
      if (st.empty()) jl[i][0] = lj[i] = -1;
      else jl[i][0] = lj[i] = st.top();
      st.push(i);
    }

    while (!st.empty()) st.pop();
    for (int i = n-1; i >= 0; i--) {
      while (!st.empty() && H[st.top()] < H[i]) st.pop();
      if (st.empty()) jr[i][0] = rj[i] = n;
      else jr[i][0] = rj[i] = st.top();
      st.push(i);
    }
  }

  void set_J() {
    jr[n][0] = jl[n][0] = n;

    for (int j = 1; j < 20; j++)
    for (int i = 0; i <= n; i++)
      jr[i][j] = jr[jr[i][j-1]][j-1];

    for (int j = 1; j < 20; j++)
    for (int i = 0; i <= n; i++)
      jl[i][j] = jl[jl[i][j-1]][j-1];
  }

  int count(int A, int B) {
    if (h[A] > h[B]) return -1;
    int ans = 0;
    for (int i = 19; i >= 0; i--)
    if (h[jr[A][i]] < h[B]) {A = jr[A][i]; ans += (1 << i);}
    if (jr[A][0] == B) return ans + 1;
    return -1;
  }
  int count(int A, int B, int C) {
    int a = A, b = B;
    A = query(max(A, lj[C] + 1), B).S;
    if (A == -1) return -1;
    
    int ans = count(A, C);
    for (int i = 19; i >= 0; i--) {
      if (jl[A][i] == -1) continue ;
      int x = count(jl[A][i], C);
      if (x != -1) ans = min(ans, (1 << i) + x);
    }
    return ans;
  }

  int count(int A, int B, int C, int D) {
    int ans = 2e9;
    int mn = query(B+1, C-1).F;
    pi s = query(C, D);
    while (s.F > mn) {
      if (s.S == -1) break ;
      int x = count(A, B, s.S);
      if (x != -1) ans = min(ans, x);
      s = query(C, s.S-1);
    }
    return (ans == 2e9 ? -1 : ans);
  }
} T;
 
void init(int N, std::vector<int> H) {
  T.n = N; T.h = H;
  T.take_J(H);
  T.build();
  T.h.pb(N + 1);
  T.set_J();

  one = 1;
  for (int i = 0; i < N; i++) if (H[i] != i+1) {one = 0; break;}
}
 
int minimum_jumps(int A, int B, int C, int D) {
  if (C == D) return T.count(A, B, C);
  if (one) return C-B;
  return T.count(A, B, C, D);
}


//ED

Compilation message

jumps.cpp: In member function 'int tree::count(int, int, int)':
jumps.cpp:85:9: warning: unused variable 'a' [-Wunused-variable]
   85 |     int a = A, b = B;
      |         ^
jumps.cpp:85:16: warning: unused variable 'b' [-Wunused-variable]
   85 |     int a = A, b = B;
      |                ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 90 ms 40496 KB Output is correct
4 Correct 688 ms 43460 KB Output is correct
5 Correct 466 ms 31228 KB Output is correct
6 Correct 598 ms 43480 KB Output is correct
7 Correct 486 ms 36056 KB Output is correct
8 Correct 590 ms 43448 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 2 ms 12884 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 3 ms 12632 KB Output is correct
6 Correct 3 ms 12632 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Incorrect 3 ms 12632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 2 ms 12884 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 3 ms 12632 KB Output is correct
6 Correct 3 ms 12632 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Incorrect 3 ms 12632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 2 ms 12632 KB Output is correct
5 Correct 38 ms 39996 KB Output is correct
6 Correct 52 ms 42676 KB Output is correct
7 Correct 21 ms 30908 KB Output is correct
8 Correct 51 ms 42696 KB Output is correct
9 Correct 8 ms 17440 KB Output is correct
10 Correct 67 ms 42720 KB Output is correct
11 Correct 48 ms 43512 KB Output is correct
12 Correct 267 ms 43216 KB Output is correct
13 Correct 102 ms 43180 KB Output is correct
14 Correct 52 ms 42584 KB Output is correct
15 Incorrect 123 ms 42952 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Incorrect 157 ms 28760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Incorrect 157 ms 28760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12632 KB Output is correct
3 Correct 90 ms 40496 KB Output is correct
4 Correct 688 ms 43460 KB Output is correct
5 Correct 466 ms 31228 KB Output is correct
6 Correct 598 ms 43480 KB Output is correct
7 Correct 486 ms 36056 KB Output is correct
8 Correct 590 ms 43448 KB Output is correct
9 Correct 3 ms 12632 KB Output is correct
10 Correct 2 ms 12884 KB Output is correct
11 Correct 2 ms 12632 KB Output is correct
12 Correct 2 ms 12632 KB Output is correct
13 Correct 3 ms 12632 KB Output is correct
14 Correct 3 ms 12632 KB Output is correct
15 Correct 3 ms 12632 KB Output is correct
16 Incorrect 3 ms 12632 KB Output isn't correct
17 Halted 0 ms 0 KB -