Submission #903576

#	Time	Username	Problem	Language	Result	Execution time	Memory
903576		efedmrlr	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	1 ms	1112 KiB

jumps

#include "jumps.h"

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 25;
const int MAXN = 2e5+5;
constexpr int MOD = 1e9+7;
int n,m,q;
vector<array<int,2> > adj;
vector<vector<int> > lift(LGN, vector<int>());
vector<vector<int> > low(LGN, vector<int>());
vector<int> h, revh(MAXN, 0);

struct SegT {
  vector<vector<array<int,2> > > data;
  int sz;
  SegT() {}
  void build(int tl, int tr, int v, vector<int> &vec) {
    if(tl == tr) {
      data[v].pb({vec[tl], tl});
      return;
    }
    int tm = (tl + tr) >> 1;
    build(tl, tm, v<<1, vec);
    build(tm + 1, tr, v<<1^1, vec);
    data[v].resize(tr - tl + 1);
    merge(all(data[v<<1]), all(data[v<<1^1]), data[v].begin());
  }
  void reset(int s, vector<int> &vec) {
    sz = s;
    data.assign(4*(s + 3), vector<array<int,2> >());
    build(0, sz - 1, 1, vec);
  }
  array<int,2>  getMax(int tl, int tr, int v, int l, int r, int x) {
    if(tl >= l && tr <= r) {
      auto itr = upper_bound(data[v].begin(), data[v].end(), array<int,2>({x, -5})) - data[v].begin();
      if(itr > 0) {
        itr--;
        return data[v][itr];
      }
      return {-INF, sz}; 
    }
    if(tl > r || tr < l) {
      return {-INF, sz};
    }
    int tm = (tl + tr) >> 1; 
    return max(getMax(tl, tm, v<<1, l, r, x), getMax(tm + 1, tr, v<<1^1, l, r, x)); 
  }
  int getMax(int l, int r, int x) {
    l = max(0, l); r = min(r, sz - 1);
    if(l > r) return sz;
    return getMax(0, sz - 1, 1, l, r, x)[1];
  }
  array<int,2> getMin(int tl, int tr, int v, int l, int r, int x) {
    if(tl >= l && tr <= r) {
      auto itr = upper_bound(data[v].begin(), data[v].end(), array<int,2>({x, -5})) - data[v].begin();
      if(itr < data[v].size()) {
        return data[v][itr];
      }
      return {INF, sz}; 
    }
    if(tl > r || tr < l) {
      return {INF, sz};
    }
    int tm = (tl + tr) >> 1; 
    return min(getMin(tl, tm, v<<1, l, r, x), getMin(tm + 1, tr, v<<1^1, l, r, x)); 
  } 
  int getMin(int l, int r, int x) {
    l = max(0, l); r = min(r, sz - 1);
    if(l > r) return sz;
    return getMin(0, sz - 1, 1, l, r, x)[1];
  }

};  
SegT sp, spr;

void init(int N, std::vector<int> H) {
  vector<array<int,2> > srt(N);
  set<int> st;
  H.pb(INF);
  h = H;
  n = N;
  sp.reset(N, h);
  for(int i = 0; i<n; i++) {
    revh[h[i]] = i; 
  }
  spr.reset(N + 1, revh);
  adj.assign(N + 5, array<int,2>({N, N}) );
  adj[N] = {N, N};
  REP(i, LGN) lift[i].assign(N + 5, N); 
  REP(i, LGN) low[i].assign(N + 5, N); 
  REP(i,N) {
    srt[i] = {H[i], i};
    st.insert(i);
  }
  sort(srt.begin(), srt.end());
  for(auto c : srt) {
    st.erase(c[1]);
    auto itr = st.lower_bound(c[1]);
    if(st.size() == 0) break;
    if(itr != st.end()) {
      adj[c[1]][1] = *itr;
    }
    if(itr != st.begin()) {
      itr--;
      adj[c[1]][0] = *itr;
    }
    if(H[adj[c[1]][0]] > H[adj[c[1]][1]]) {
      swap(adj[c[1]][0], adj[c[1]][1]);

    }
  }
  for(int i = 0; i<n; i++) {
    lift[0][i] = adj[i][1];
    low[0][i] = adj[i][0];
    
  }
  for(int k = 1; k<LGN; k++) {
    for(int i = 0; i<n; i++) {
      lift[k][i] = lift[k - 1][lift[k - 1][i]];
      low[k][i] = low[k - 1][low[k - 1][i]];
    }
  } 
}

int solve(int A, int C) {
  if(h[A] > h[C]) return -1;
  int ans = 0;
  for(int i = LGN - 1; i>=0; i--) {
    if(h[ lift[i][A] ] <= h[C]) {
      ans += 1<<i;
      A = lift[i][A];
    }
  } 
  for(int i = LGN - 1; i>=0; i--) {
    if(h[ low[i][A] ] <= h[C]) {
      ans += 1<<i;
      A = low[i][A];
    }
  }
  if(A != C) return -1;
  
  return ans;
}

int minimum_jumps(int A, int B, int C, int D) {

  int cmax = sp.getMax(C, D, INF);
  int mx = (B + 1 > C - 1) ? h[sp.getMax(B + 1, C - 1, INF)] : -1;
  if(mx > h[cmax] ) return -1;
  int ableft = spr.getMax(h[cmax] + 1, n, B + 1);
  if(ableft == n) ableft = -1;
  else ableft = revh[ableft];
  A = max(A , ableft + 1);
  int ab = sp.getMax(A, B, h[cmax]);
  // cout<<"cmax:" <<cmax<<" mx:"<<mx<<" ab:"<<ab<<endl;
  // cout<<"ableft:"<<ableft<<"\n";
  if(ab == n) return -1;
  
  
  return solve(ab, cmax);
}

Compilation message (stderr)

jumps.cpp: In member function 'std::array<int, 2> SegT::getMin(int, int, int, int, int, int)':
jumps.cpp:78:14: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |       if(itr < data[v].size()) {
      |          ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19