oj.uz

Submission #974229

# Submission time Handle Problem Language Result Execution time Memory
974229 2024-05-03T06:35:31 Z AlperenT_ Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 208 ms 69380 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 > B && x < C)while(1){}
    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 165 ms 63052 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.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 4 ms 13136 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 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 4 ms 13136 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 3 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 74 ms 56540 KB Output is correct
6 Correct 109 ms 60976 KB Output is correct
7 Correct 44 ms 40536 KB Output is correct
8 Correct 94 ms 60960 KB Output is correct
9 Correct 10 ms 21848 KB Output is correct
10 Correct 102 ms 60788 KB Output is correct
11 Correct 83 ms 69380 KB Output is correct
12 Incorrect 80 ms 67812 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 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 208 ms 38120 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 12888 KB Output is correct
3 Correct 2 ms 12888 KB Output is correct
4 Incorrect 208 ms 38120 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 165 ms 63052 KB Output isn't correct
4 Halted 0 ms 0 KB -