oj.uz

Submission #974244

# Submission time Handle Problem Language Result Execution time Memory
974244 2024-05-03T06:44:18 Z AlperenT_ Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 972 ms 69368 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(answer(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++;
    }
  }else{
    ans = inf ;
  }
  ans = min(ans, answer(id2 , l));
  return ans ;
}

Subtask #1
4.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 Correct 144 ms 63312 KB Output is correct
4 Correct 945 ms 69252 KB Output is correct
5 Correct 730 ms 44612 KB Output is correct
6 Correct 972 ms 69368 KB Output is correct
7 Correct 680 ms 57260 KB Output is correct
8 Correct 955 ms 69316 KB Output is correct

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 3 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 3 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 2 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Correct 3 ms 12896 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 72 ms 56400 KB Output is correct
6 Correct 87 ms 60812 KB Output is correct
7 Correct 46 ms 40456 KB Output is correct
8 Correct 88 ms 60752 KB Output is correct
9 Correct 10 ms 21848 KB Output is correct
10 Correct 89 ms 60956 KB Output is correct
11 Correct 93 ms 69268 KB Output is correct
12 Correct 81 ms 67592 KB Output is correct
13 Correct 82 ms 67332 KB Output is correct
14 Correct 92 ms 61148 KB Output is correct
15 Correct 104 ms 68864 KB Output is correct
16 Correct 85 ms 69096 KB Output is correct
17 Correct 87 ms 69104 KB Output is correct
18 Correct 2 ms 12888 KB Output is correct
19 Correct 2 ms 12888 KB Output is correct
20 Incorrect 2 ms 12888 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12680 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Incorrect 146 ms 37980 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 12888 KB Output is correct
2 Correct 2 ms 12680 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Incorrect 146 ms 37980 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 Correct 144 ms 63312 KB Output is correct
4 Correct 945 ms 69252 KB Output is correct
5 Correct 730 ms 44612 KB Output is correct
6 Correct 972 ms 69368 KB Output is correct
7 Correct 680 ms 57260 KB Output is correct
8 Correct 955 ms 69316 KB Output is correct
9 Correct 2 ms 12888 KB Output is correct
10 Correct 2 ms 12888 KB Output is correct
11 Correct 3 ms 12888 KB Output is correct
12 Correct 2 ms 12888 KB Output is correct
13 Correct 3 ms 12888 KB Output is correct
14 Incorrect 3 ms 12888 KB Output isn't correct
15 Halted 0 ms 0 KB -