제출 #980419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
980419		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	37 / 100	4072 ms	20324 KiB

jumps

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#include "jumps.h"

using namespace std;
set<pair<int, int>> lf, rg;
vector<int> g[200005]; 
int n;
int mx[4 * 200005], mn[4 * 200005];
void up(int l, int r, int ind, int num, int v){
  if(l > ind || r < ind) return;
  if(l == r){
    mx[v] = num;
    return;
  }
  int mid = (l + r) / 2;
  up(l, mid, ind, num, v * 2);
  up(mid + 1, r, ind, num, v * 2 + 1);
  mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
}
int get_mx(int l, int r, int l1, int r1, int v){
  if(l > r1 || l1 > r) return 0;
  if(l >= l1 && r1 >= r) return mx[v];
  int mid = (l + r) / 2;
  return max(get_mx(l, mid, l1, r1, v * 2), get_mx(mid + 1, r, l1, r1, v * 2 + 1));
}
bool ok = 0;
void init(int N, std::vector<int> H) {
    n = N;
    for(int i = 0; i < N; i++){
      up(1, n, i + 1, H[i], 1);
      if(H[i] != i + 1) ok = 1;
    }
    for(int i = 1; i <= n; i++){
      int L = 0, R = i;
      while(L + 1 < R){
        int mid = (L + R) / 2;
        if(get_mx(1, n, mid, i, 1) > H[i - 1]) L = mid;
        else R = mid;
      }
      if(L != 0) g[i].push_back(L);
      L = i, R = n + 1;
      while(L + 1 < R){
        int mid = (L + R) / 2;
        if(get_mx(1, n, i, mid, 1) > H[i - 1]) R = mid;
        else L = mid;
      }
      if(R != n + 1) g[i].push_back(R);
    }
}
int dist[200005];
bool us[200005];
int minimum_jumps(int A, int B, int C, int D) {
  A++;
  B++;
  C++;
  D++;
  if(!ok) return C - B;
  for(int i = 1; i <= n; i++){
    us[i] = 0;
    dist[i] = 0;
  }
  deque<int> d; 
  for(int i = A; i <= B; i++){
    d.push_back(i);
    us[i] = 1;
  }
  int mn = 2e9;
  while(!d.empty()){
    int num = d.front();
    if(num >= C && num <= D) mn = min(mn, dist[num]);
    d.pop_front();
    for(int to : g[num]){
      if(!us[to]){
        us[to] = 1;
        dist[to] = dist[num] + 1;
        d.push_back(to);
      }
    }
  }
  if(mn == 2e9) return -1;
  else return mn; 
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19