Submission #887821

#	Time	Username	Problem	Language	Result	Execution time	Memory
887821		Iliya_	Rainforest Jumps (APIO21_jumps)	C++14	81 / 100	4021 ms	57944 KiB

jumps

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll; 
typedef long double dll;

const int N = 2e5+7, lg = 23, inf = 1e9; 
vector<int> g[N],vec;
vector<pii> sor; 
int dist[N], n, hi[N], seg[N<<2], sm[lg][N], big[lg][N], l[N], r[N];
bool sub1 = false; 
queue<int> q;
//#include "jumps.h"

void build(int ind = 1, int l = 0, int r = n-1){
     if (l == r){
          seg[ind] = hi[l]; 
          return; 
     }
     int mid = (l+r)>>1; 
     build(2*ind,l,mid);
     build(2*ind+1,mid+1,r); 
     seg[ind] = max(seg[2*ind],seg[2*ind+1]);
}

int get(int st, int en, int ind = 1, int l = 0, int r = n-1){
     if (l > en || st > r) return 0; 
     if (l == r || (l >= st && r <= en)) return seg[ind]; 
     int mid = (l+r)>>1;
     return max(get(st,en,2*ind,l,mid),get(st,en,2*ind+1,mid+1,r));
}

void init(int _n, vector<int> h){
     n = _n;
     for(int i=0; i<n; i++){
          hi[i] = h[i]; 
          sor.pb({h[i],i}); 
     }
     sort(all(sor));
     sub1 = true; 
     for(int i=0; i<n; i++) if (h[i] != i+1) sub1 = false; 
     vec.pb(0);
     l[0] = -1;
     for(int i=0; i<n; i++){
          while(vec.size() && h[vec.back()] < h[i]) vec.pop_back();
          if (vec.size()){
               g[i].pb(vec.back());
               l[i] = vec.back(); 
          }
          else l[i] = -1; 
          vec.pb(i);
     }
     vec.clear();
     vec.pb(n-1);
     r[n-1] = -1;
     for(int i=n-2; i>=0; i--){
          while(vec.size() && h[vec.back()] < h[i]) vec.pop_back();
          if (vec.size()){
               g[i].pb(vec.back());
               r[i] = vec.back(); 
          }
          else r[i] = -1;
          vec.pb(i); 
     }
     build(); 
     for(int j=0; j<lg; j++) for(int i=0; i<n; i++) big[j][i] = sm[j][i] = -1;
     for(int i=0; i<n; i++){
          if (l[i] != -1) big[0][i] = l[i]; 
          if (r[i] != -1){
               if (big[0][i] == -1 || h[big[0][i]] < h[r[i]]){
                    sm[0][i] = big[0][i]; 
                    big[0][i] = r[i];
               }
               else sm[0][i] = r[i]; 
          }
     }
     for(int j=1; j<lg; j++){
          for(int i=0; i<n; i++){
               if (big[j-1][i] != -1) big[j][i] = big[j-1][big[j-1][i]]; 
               if (sm[j-1][i] != -1) sm[j][i] = sm[j-1][sm[j-1][i]]; 
          }
     }
}

int sub56(int st, int en){
     if (hi[st] > hi[en] || get(st+1,en-1) > hi[en]) return -1;
     int ans = 0; 
     int v = st; 
     for(int i=lg-1; i>=0; i--){
          if (big[i][v] != -1 && hi[big[i][v]] <= hi[en]){
               v = big[i][v]; 
               ans += (1<<i); 
          }
     }
     for(int i=lg-1; i>=0; i--){
          if (sm[i][v] != -1 && hi[sm[i][v]] <= hi[en]){
               v = sm[i][v]; 
               ans += (1<<i); 
          }
     }
     return ans; 
}

int minimum_jumps(int a, int b, int c, int d){
     if (sub1) return c-b; 
     if (c == d){ 
          int l = a-1, r = b; 
          while(r-l>1){
               int mid = (l+r)>>1;
               if (get(mid,b)<hi[c]) r = mid; 
               else l = mid; 
          }
          pii wef = {get(r,b),0};
          int ind = lower_bound(all(sor),wef)-sor.begin();
          ind = sor[ind].S; 
          return sub56(ind,c);
     }     
     fill(dist,dist+n,inf);
     for(int i=a; i<=b; i++){
          dist[i] = 0;
          q.push(i); 
     }
     while(q.size()){
          int v = q.front(); q.pop();
          for(int u : g[v]){
               if (dist[u] > dist[v] + 1){
                    dist[u] = dist[v] + 1; 
                    q.push(u); 
               }
          }
     }
     int mn = inf;
     for(int i=c; i<=d; i++) mn = min(mn,dist[i]);
     return (mn == inf ? -1 : mn);
}

/*
int32_t main(){
     fast_io;
     vector<int> tmp = {3, 2, 1, 6, 4, 5, 7};
     init(7, tmp);
     cout << minimum_jumps(4, 4, 6, 6) << endl;
     cout << minimum_jumps(0, 1, 2, 2) << endl;
     return 0;
}
*/

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