oj.uz

Submission #980723

# Submission time Handle Problem Language Result Execution time Memory
980723 2024-05-12T10:56:19 Z vjudge1 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1058 ms 57644 KB 
#include "jumps.h"
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define ff first
#define ss second
const int mod = 1e9 + 7;
const int inf = 1e9;
const int logn = 20;

template<typename T>
int len(T &a){return a.size();}


vector<vector<int>> up, low;

int n;
bool sub1 = 1;



vector<int> h; vector<int> pos;

struct SparseT{
  vector<vector<int>> t;
  int n, logn;
  int join(int a, int b){
    return max(a,b);
  }

  int neutral(){
    return 0;
  }

  SparseT (){}

  SparseT (int _n){
    init(_n);
  }

  SparseT (vector<int> &a){
    build(a);
  }

  void init(int _n){
    n = _n;
    logn = 32 - __builtin_clz(n);
    t.assign(_n, vector<int>(logn, neutral()));
  }

  void build(vector<int> &a){
    init((int)(a.size()));
    for(int i = 0; i < n; i ++){
      t[i][0] = a[i];
    }

    for(int i = 1; i < logn; i ++){
      for(int j = 0; j + (1 << i) <= n; j ++){
        t[j][i] = join(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]);
      }
    }
  }

  int get(int l, int r){
    if(l > r) return neutral();
    int k = 31 - __builtin_clz(r - l + 1);
    return join(t[l][k], t[r - (1 << k) + 1][k]); 
  }
} t;


void init(int N, vector<int> H) {
  h = H;
  n = N;
  pos.resize(n);

  for(int i = 0; i < n; i ++) h[i] --;
  for(int i = 0; i < n; i ++) pos[h[i]] = i;
  vector<int> st;
  vector<int> lef(n), rig(n);
  for(int i = 0; i < n; i ++){
    if(h[i] != i + 1) sub1 = 0;
    while(!st.empty() && st.back() <= h[i]) st.pop_back();
    if(st.empty()) lef[i] = -1;
    else lef[i] = st.back();
    st.push_back(h[i]);
  }
  if(sub1) return;
  st.clear();
  for(int i = n - 1; i >= 0; i --){
    while(!st.empty() && st.back() <= h[i]) st.pop_back();
    if(st.empty()) rig[i] = -1;
    else rig[i] = st.back();
    st.push_back(h[i]);
  }

  up.assign(logn, vector<int> (n, -1));
  low.assign(logn, vector<int> (n, -1));

  for(int i = 0; i < n; i ++){
    up[0][h[i]] = max(lef[i], rig[i]);
  }
  t.build(h);
  // first max, then min
  for(int j = 1; j < logn; j ++){
    for(int i = 0; i < n; i ++){
      if(up[j - 1][i] == -1) continue;
      //cout << (up[j][i]) << endl;
      up[j][i] = up[j - 1][up[j - 1][i]];
    }
  }

  for(int i = 0; i < n; i ++){
    if(lef[i] == -1 && rig[i] == -1) continue;
    if(lef[i] == -1) low[0][h[i]] = rig[i];
    else if(rig[i] == -1) low[0][h[i]] = rig[i];
    else low[0][h[i]] = min(rig[i], lef[i]);
  }

  for(int j = 1; j < logn; j ++){
    for(int i = 0; i < n; i ++){
      if(low[j - 1][i] == -1) continue;
      low[j][i] = low[j - 1][low[j - 1][i]];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  if(sub1) return C - B;
  int obst = t.get(B, C - 1);
  int mxx = t.get(C, D);
  if(mxx <= obst) return -1;


  int l = A - 1, r = B;
  while(r - l > 1){
    int m = (l + r) / 2;
    if(t.get(m, C - 1) < mxx){
      r = m;
    }else l = m;
  }
  int ans = 0;
  int st = t.get(r, B);

  for(int j = logn - 1; j >= 0; j --){
    if(up[j][st] != -1 && up[j][st] <= obst){
      ans += 1 << j;
      st = up[j][st];
    }
  }
  if(st == obst){
    return ans + 1;
  }
  if(up[0][st] <= mxx){
    if(C <= pos[up[0][st]] && pos[up[0][st]] <= D){
      return ans + 1;
    }
    return ans + 2;
  }
  for(int j = logn - 1; j >= 0; j --){
    if(low[j][st] != -1 && low[j][st] <= obst){
      st = up[j][st];
      ans += 1 << j;
    }
  }
  return ans + 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 147 ms 45856 KB Output is correct
4 Correct 1058 ms 57632 KB Output is correct
5 Correct 778 ms 29156 KB Output is correct
6 Correct 1002 ms 57620 KB Output is correct
7 Correct 764 ms 39468 KB Output is correct
8 Correct 1039 ms 57616 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 61 ms 45740 KB Output is correct
6 Correct 81 ms 56756 KB Output is correct
7 Correct 37 ms 29104 KB Output is correct
8 Correct 82 ms 56748 KB Output is correct
9 Correct 9 ms 8736 KB Output is correct
10 Correct 82 ms 56880 KB Output is correct
11 Correct 73 ms 57644 KB Output is correct
12 Incorrect 70 ms 57424 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 156 ms 26280 KB Output is correct
5 Incorrect 661 ms 56636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 156 ms 26280 KB Output is correct
5 Incorrect 661 ms 56636 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 147 ms 45856 KB Output is correct
4 Correct 1058 ms 57632 KB Output is correct
5 Correct 778 ms 29156 KB Output is correct
6 Correct 1002 ms 57620 KB Output is correct
7 Correct 764 ms 39468 KB Output is correct
8 Correct 1039 ms 57616 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Incorrect 1 ms 344 KB Output isn't correct
15 Halted 0 ms 0 KB -