oj.uz

답안 #971380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971380 2024-04-28T12:32:14 Z AlperenT_ 밀림 점프 (APIO21_jumps) C++17
0 / 100
 4000 ms 46736 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 ];
vector< int> G[maxn] ;

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){
      id = i ;
      continue ;
    }
    if(L[i]!=-1 && (R[i] == -1 || h[L[i]] < h[R[i]])){
      G[L[i]].pb(i) ;par2[i] = L[i] ;
      if(R[i] == -1)par[i][0] = L[i] ;
      else par[i][0] = R[i] ;
    }else{
      G[R[i]].pb(i) ;par2[i] = R[i] ;
      if(L[i] == -1)par[i][0] = R[i] ;
      else par[i][0] = L[i] ;
    }
  }
  dfs(id) ;
  rep(i ,1 ,n){
    rep(j , 1 ,lg){
      par[i][j] = par[par[i][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);
    }
  }
  while(a != b){
    ans ++ ;
    a = par2[a] ;
  }
  return ans;
}

int minimum_jumps(int A, int B, int C, int D) {
  A++;B++;C++;D++;
  int ans = inf ;
  rep(i , A ,B){
    rep(j, C , D){
      ans = min(ans , answer(i , j)) ;
    }
  }
  return (ans == inf ? -1 : ans)  ;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Execution timed out 4061 ms 46736 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 11084 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 3 ms 10840 KB Output is correct
11 Correct 37 ms 10840 KB Output is correct
12 Correct 22 ms 10840 KB Output is correct
13 Correct 10 ms 10840 KB Output is correct
14 Correct 4 ms 10840 KB Output is correct
15 Incorrect 15 ms 10840 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 11084 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 3 ms 10840 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 3 ms 10840 KB Output is correct
11 Correct 37 ms 10840 KB Output is correct
12 Correct 22 ms 10840 KB Output is correct
13 Correct 10 ms 10840 KB Output is correct
14 Correct 4 ms 10840 KB Output is correct
15 Incorrect 15 ms 10840 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 321 ms 39928 KB Output is correct
6 Execution timed out 4026 ms 46212 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Incorrect 127 ms 29900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10840 KB Output is correct
3 Correct 2 ms 10840 KB Output is correct
4 Incorrect 127 ms 29900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10840 KB Output is correct
3 Execution timed out 4061 ms 46736 KB Time limit exceeded
4 Halted 0 ms 0 KB -