제출 #528618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528618		DanerZein	밀림 점프 (APIO21_jumps)	C++14	12 / 100	1470 ms	15704 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAX_N=2e5+10;
const int MAX_P=MAX_N*4;
int st[MAX_P];
int val[MAX_N];
int dis[MAX_N];
int n;
vector<vi> G;
void init(int node,int a,int b){
  if(a==b){
    st[node]=val[a];
    return;
  }
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  init(le,a,mid);
  init(ri,mid+1,b);
  st[node]=max(st[le],st[ri]);
}
int query(int node,int a,int b,int l,int r){
  if(b<l || a>r) return 0;
  if(l<=a && r>=b) return st[node];
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  return max(query(le,a,mid,l,r),query(ri,mid+1,b,l,r));
}
int izquier(int x){
  int q=query(0,0,n-1,0,x);
  if(q==val[x]) return -1;
  int l=0,r=x;
  while(r-l>1){
    int mid=(l+r)/2;
    q=query(0,0,n-1,mid,r);
    if(q>val[x])
      l=mid;
    else r=mid;
  }
  return l;
}
int derecha(int x){
  int q=query(0,0,n-1,x,n-1);
  if(q==val[x]) return -1;
  int l=x,r=n-1;
  while(r-l>1){
    int mid=(l+r)/2;
    q=query(0,0,n-1,l,mid);
    if(q>val[x]) r=mid;
    else l=mid;
  }
  return r;
}
void init(int N, std::vector<int> H) {
  for(int i=0;i<N;i++) val[i]=H[i];
  G.resize(N+1);
  n=N;
  init(0,0,n-1);
  for(int i=0;i<n;i++){
    int l=izquier(i);
    int r=derecha(i);
    // cout<<i<<": "<<l<<" "<<r<<endl;
    if(l!=-1) G[i].push_back(l);
    if(r!=-1) G[i].push_back(r);
  }
}
bool iq[MAX_N];
void bfs(int u){
  for(int i=0;i<n;i++) {
    dis[i]=1e9;
    iq[i]=0;
  }
  dis[u]=0;
  iq[u]=1;
  queue<int> q;
  q.push(u);
  while(!q.empty()){
    int x=q.front();
    iq[x]=0;
    q.pop();
    for(auto &v:G[x]){
      if(dis[v]>dis[x]+1){
	dis[v]=dis[x]+1;
	if(!iq[v]){
	  q.push(v);
	  iq[v]=1;
	}
      }
    }
  }
}
int minimum_jumps(int A, int B, int C, int D) {
  if(n>200){
    return C-B;
  }
  int res=1e9;
  for(int i=A;i<=B;i++){
    bfs(i);
    for(int j=C;j<=D;j++){
      res=min(res,dis[j]);
    }
  }
  if(res>=1e9) res=-1;
  return res;
}

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