oj.uz

Submission #974225

# Submission time Handle Problem Language Result Execution time Memory
974225 2024-05-03T06:30:40 Z AlperenT_ Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 164 ms 69300 KB 
#include "jumps.h"
 
#include <vector>
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
const int maxn = 2e5 + 10 , maxq = 32, inf = 1e9+10 , lg = 19  ,sq = 707 ,mod = 998244353 ;
int mx[maxn][lg+1] , c = 1 , L[maxn] , R[maxn], h[maxn] , dis[maxn] , par[maxn][lg+1] , par2[maxn][lg+1];
vector< int> G[maxn] ;
int ch(int l , int r){
  int x = 31 - __builtin_clz(r-l+1) ; 
  return (h[mx[l][x]] > h[mx[r-(1<<x)+1][x]] ? mx[l][x] : mx[r-(1<<x)+1][x]) ;
}
void dfs(int v){
  for(int u : G[v]){
    dis[u] = dis[v] + 1; 
    dfs(u) ;
  }
}
 
void init(int n, vector<int> H) {
  rep(i ,1 ,n){
    h[i] = H[i-1] ;
    mx[i][0] = i ;
  }
  vector <int> vec;;
  rep(i , 1, n){
    while(sz(vec) && h[vec.back()] < h[i])vec.pop_back() ;
    L[i] = -1 ;
    if(sz(vec)!=0)L[i] = vec.back() ;
    vec.pb(i) ;
  }
  vec.clear() ;
  per(i ,n,1){
    while(sz(vec) && h[vec.back()] < h[i])vec.pop_back() ;
    R[i] = -1 ;
    if(sz(vec)!=0)R[i] = vec.back() ;
    vec.pb(i) ;
  }
  int id =0 ;
  rep(i ,1 ,n){
    if(L[i]+R[i] == -2){
      par2[i][0] = n+1 ;
      id = i ;
      continue ;
    }
    if(R[i] == -1)par2[i][0] =n +1 ;
    else par2[i][0] = R[i] ;
    if(L[i]!=-1 && (R[i] == -1 || h[L[i]] < h[R[i]])){
      G[L[i]].pb(i) ;
      if(R[i] == -1)par[i][0] = L[i] ;
      else par[i][0] = R[i] ;
    }else{
      G[R[i]].pb(i) ;
      if(L[i] == -1)par[i][0] = R[i] ;
      else par[i][0] = L[i] ;
    }
  }
  rep(i , 0 ,lg)par2[n+1][i] = n+1 ;
  dfs(id) ;
  rep(j , 1 ,lg){
    rep(i ,1 ,n){
      par2[i][j] = par2[par2[i][j-1]][j-1] ;
      par[i][j] = par[par[i][j-1]][j-1];
      if(i+(1<<(j-1))>n){
        mx[i][j] = mx[i][j-1] ;
      }else{
        mx[i][j] = (h[mx[i][j-1]] > h[mx[i+(1<<(j-1))][j-1]] ? mx[i][j-1] : mx[i+(1<<(j-1))][j-1]);
      }
    }
  }
}
 
int answer(int a, int b){
  if(L[b] >= a)return inf ;
  int ans =0 ;
  per(i , lg , 0){
    if(par[a][i] != 0 && h[par[a][i]] <= h[b]){
      a = par[a][i] ;
      ans += (1<<i);
    }
  }
  ans += dis[a]-dis[b] ;
  return ans;
}
 
 
int minimum_jumps(int A, int B, int C, int D) {
  A++;B++;C++;D++;
  int id = ch(C , D) ;
  A = max(A,  max(0,L[id])+1) ;
  if(B < A)return -1 ;
  int id2 = ch(A, B);int ans = 0 ;
  if(ch(id2 ,id) == inf)return -1 ;
  int x = id2 ;
  per(i , lg , 0){
    if(par2[x][i] < C){
        x =par2[x][i] ;
    }
  }
  x = par2[x][0] ;
  int l = x  ;
  x=id2 ;
  per(i , lg , 0){
    if(par[x][i] != 0 && dis[par[x][i]] > dis[l]){
        x =par[x][i]; 
        ans += (1<<i) ;
    }
  }
  if(par[x][0] >= dis[id]){
    ans++;
    x = par[x][0] ;
    if(!(x >= C && x <= D))ans++;
  }
  ans = min(ans, answer(id2 , l));
  return ans ;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Incorrect 149 ms 63056 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13140 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12900 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 70 ms 56524 KB Output is correct
6 Correct 92 ms 60768 KB Output is correct
7 Correct 49 ms 40476 KB Output is correct
8 Correct 94 ms 60964 KB Output is correct
9 Correct 10 ms 21848 KB Output is correct
10 Correct 88 ms 60960 KB Output is correct
11 Correct 91 ms 69300 KB Output is correct
12 Incorrect 85 ms 67584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13044 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Incorrect 164 ms 38128 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 13044 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Incorrect 164 ms 38128 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 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Incorrect 149 ms 63056 KB Output isn't correct
4 Halted 0 ms 0 KB -