제출 #418763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418763		REALITYNB	밀림 점프 (APIO21_jumps)	C++14	0 / 100	1 ms	200 KiB

jumps

#include <bits/stdc++.h>
#define mp make_pair
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int mxn = 20001, mxl = 20;
int n, l[mxn][mxl], r[mxn][mxl];
vector<int> h;
int HE[mxn][mxl];
int good(int x){
  return (0<=x&&x<n);
}
void init(int mxn, vector<int> H){
  vector<pii> sHE;
  set<int> bull;
  for(int i=0;i<n;i++) sHE.push_back(mp(h[i],i));
  n=mxn,h=H;
  sort(all(sHE)) ;
  reverse(all(sHE));
  bull.insert(n); bull.insert(-1);
  for(int i=0;i<mxn;++i)for(int j=0;j<mxl;j++)l[i][j]=r[i][j]=HE[i][j]=-1;
  for (auto xxx : sHE){
  	int i=xxx.S ;
    auto it=bull.lower_bound(i);
    r[i][0]=*it,l[i][0]=*(--it);
    bull.insert(i);
    if(!good(l[i][0])&&!good(r[i][0]));
    else if(!good(r[i][0])) HE[i][0]=l[i][0];
    else if(!good(l[i][0])) HE[i][0]=r[i][0];
    else if(h[l[i][0]] > h[r[i][0]]) HE[i][0]=l[i][0];
    else HE[i][0]=r[i][0];
  }
  for(int j=0; j<mxl-1;j++){
    for(int i=0;i<n;i++){
      if(good(l[i][j])) l[i][j+1]=l[l[i][j]][j];
      if(good(HE[i][j]))HE[i][j+1]=HE[HE[i][j]][j];
      if(good(r[i][j])) r[i][j+1]=r[r[i][j]][j];
    }
  }
}
int tgo(int bull[mxn][mxl],int &s, function<int(int)> cond){
	  int rs=0;
	  for(int i=mxl-1;i>-1;i--){
	    if(good(bull[s][i])&&cond(bull[s][i])){
	      s=bull[s][i],rs+=(1<<i);
	    }
	  }
	  return rs;
};
int A,B,C,D ;
int cmp(int x){
    return good(r[x][0])&&r[x][0]<C;
}
int cmp1(int x){
    return x<C ;
}
int cmp0(int x){
    return A<=x&&r[x][0]<=D&&good(r[x][0]);
}
int minimum_jumps(int AA, int BB, int CC, int DD){
    A=AA,B=BB,C=CC,D=DD;
    int shes = B;
	tgo(l,shes,cmp0);
    int ans = tgo(HE,shes,cmp);
    if(r[shes][0]<C&&good(r[shes][0])&&good(r[HE[shes][0]][0])&&good(HE[shes][0])&&r[HE[shes][0]][0]<=D){
	      shes=HE[shes][0];
	      ans++;
    }
	ans += tgo(r,shes,cmp1);
   if(r[shes][0]<=D&&r[shes][0]>=C) return ++ans;
   return -1 ;
}

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