Submission #1052068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052068		Zbyszek99	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	530 ms	6860 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define size(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int next_[200001];
int prev_[200001];
int h[200001];
int odl[200001];
bitset<200001> odw;
int n;
bool subtask1 = true;

void init(int N, vector<int> H) 
{
  n = N;
  rep(i,n) h[i] = H[i];
  vector<pii> q;
  rep(i,n)
  {
    if(i == 0)
    {
      if(h[i] < h[i-1]) subtask1 = false;
    }
    while(size(q) > 0 && h[i] > q.back().ff) q.pop_back();
    if(size(q) != 0)
    {
      prev_[i] = q.back().ss;
    } 
    else prev_[i] = i;
    q.pb({h[i],i});
  }
  q = {};
  for(int i = n-1; i >= 0; i--)
  {
    while(size(q) > 0 && h[i] > q.back().ff) q.pop_back();
    if(size(q) != 0)
    {
      next_[i] = q.back().ss;
    } 
    else next_[i] = i;
    q.pb({h[i],i});
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  if(!subtask1)
  {
    rep(i,n) odl[i] = 1e9;
    rep(i,n) odw[i] = 0;
    rep2(i,A,B) odl[i] = 0;
    queue<int> kol; 
    rep2(i,A,B) kol.push(i);
    int wyn = 1e9;
    while(!kol.empty())
    {
      int t = kol.front();
      kol.pop();
      if(odw[t] == 1) continue;
      if(t >= C && t <= D) wyn = min(wyn,odl[t]);
      odl[next_[t]] = min(odl[next_[t]],odl[t]+1);
      odl[prev_[t]] = min(odl[prev_[t]],odl[t]+1);
      kol.push(next_[t]);
      kol.push(prev_[t]);
      odw[t] = 1;
    }
    if(wyn == 1e9) return -1;
    return wyn;
  }
  else
  {
    int ans = 1e9;
    if(C-B >= 0) ans = C-B;
    if(C <= B) ans = 0;
    if(ans == 1e9) return -1;
    return ans;    
  }
  return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:41:22: warning: array subscript -1 is below array bounds of 'int [200001]' [-Warray-bounds]
   41 |       if(h[i] < h[i-1]) subtask1 = false;
      |                 ~~~~~^

• Subtask 1: 4 / 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