Submission #979887

#	Time	Username	Problem	Language	Result	Execution time	Memory
979887		Malix	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	4069 ms	41196 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair

int INF=1e9+10;
vii R,L;

void init(int n, std::vector<int> a) {
  int m=log2(n);
  L.resize(n,vi(m+2,INF));
  R.resize(n,vi(m+2,INF));
  
  priority_queue<pi,vector<pi>,greater<pi>> pq;
  pq.push({a[0],0});
  REP(i,1,n){
    while(!pq.empty()&&pq.top().F<a[i]){
      R[pq.top().S][0]=i;
      pq.pop();
    }
    pq.push({a[i],i});
  }
  pq=priority_queue<pi,vector<pi>,greater<pi>>();
  pq.push({a[n-1],n-1});
  for(int i=n-2;i>=0;i--){
    while(!pq.empty()&&pq.top().F<a[i]){
      L[pq.top().S][0]=i;
      pq.pop();
    }
    pq.push({a[i],i});
  }
  //cout<<R[3][0];
  //REP(i,0,n){
    //cout<<L[i][0]<<" ";
    //cout<<R[i][0]<<" ";
    //cout<<"\n";
  //}
  REP(i,1,m+1){
    REP(j,0,n){
      if(L[j][i-1]!=INF)L[j][i]=min(L[j][i],L[L[j][i-1]][i-1]);
      if(R[j][i-1]!=INF)L[j][i]=min(L[j][i],L[R[j][i-1]][i-1]);
      if(L[j][i-1]!=INF)R[j][i]=max(L[j][i],R[L[j][i-1]][i-1]);
      if(R[j][i-1]!=INF)R[j][i]=max(L[j][i],R[R[j][i-1]][i-1]);
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  int ans=INF;
  REP(j,C,D+1)REP(i,A,B+1){
    //cout<<i<<"-";
    int c2=0;
    int it=lower_bound(R[i].begin(),R[i].end(),j)-R[i].begin();
    //cout<<R[A][it]<<it<<" "<<"\n";
    //cout<<R[3][0]<<"\n";
    if(j==R[i][it]){
      //cout<<it<<" ";
      ans=pow(2,it);
      continue;
    }
    if(it==0){
      c2=0;
      continue;
    }
    c2+=pow(2,it-1);
    int t=R[i][it-1];
    bool f=1;
    //cout<<"a";
    while(f){
      int it2=lower_bound(R[t].begin(),R[t].end(),j)-R[t].begin();
      //cout<<it2<<" ";
      if(j==R[t][it2]){
        c2+=pow(2,it2);
        f=0;
        break;
      }
      else{
        if(it2==0){
          c2=0;
          f=0;
          break;
        }
        c2+=pow(2,it2-1);
        t=R[t][it2-1];
      }
    }
    //cout<<"a";
    if(c2!=0)ans=min(c2,ans);
    //cout<<i<<" "<<ans<<"\n";
    //cout<<"\n";
  }
  //cout<<ans;
  if(ans==0||ans==INF)return -1;
  return ans;
}

• 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