oj.uz

Submission #974258

# Submission time Handle Problem Language Result Execution time Memory
974258 2024-05-03T06:56:19 Z AlperenT_ Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 948 ms 69372 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 188 ms 63076 KB Output is correct
4 Correct 930 ms 69368 KB Output is correct
5 Correct 756 ms 44648 KB Output is correct
6 Correct 932 ms 69372 KB Output is correct
7 Correct 743 ms 57348 KB Output is correct
8 Correct 948 ms 69328 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 12920 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 12920 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 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 3 ms 12888 KB Output is correct
5 Correct 71 ms 56308 KB Output is correct
6 Correct 86 ms 61040 KB Output is correct
7 Correct 47 ms 40464 KB Output is correct
8 Correct 89 ms 60952 KB Output is correct
9 Correct 10 ms 21848 KB Output is correct
10 Correct 88 ms 60816 KB Output is correct
11 Correct 84 ms 69360 KB Output is correct
12 Correct 83 ms 67612 KB Output is correct
13 Correct 86 ms 67308 KB Output is correct
14 Correct 89 ms 60932 KB Output is correct
15 Correct 108 ms 68852 KB Output is correct
16 Correct 81 ms 69108 KB Output is correct
17 Correct 82 ms 69120 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 3 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 Incorrect 174 ms 38080 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Incorrect 174 ms 38080 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 188 ms 63076 KB Output is correct
4 Correct 930 ms 69368 KB Output is correct
5 Correct 756 ms 44648 KB Output is correct
6 Correct 932 ms 69372 KB Output is correct
7 Correct 743 ms 57348 KB Output is correct
8 Correct 948 ms 69328 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 12920 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 -