Submission #561644

#	Time	Username	Problem	Language	Result	Execution time	Memory
561644		Omar_Elgedawy	Rainforest Jumps (APIO21_jumps)	C++14	8 / 100	4088 ms	165668 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define cin(vec)        for(auto& i : vec) cin >> i
#define cout(vec)       for(auto& i : vec) cout << i << " "; cout << "\n";
#define fast            ios::sync_with_stdio(0);cin.tie(0);
#define loop(i,a,b)     for (int i = a; i < b; i++)
#define F               first
#define S               second
#define pb(n)           push_back(n)
#define pf(n)           push_front(n)
#define dci(d)          fixed<<setprecision(d)
#define sp              ' '
#define el              '\n'
#define all(v)          v.begin(),v.end()
// #define int             long long
int dx[8]= {0,0,1,-1,-1,1,1,-1};
int dy[8]= {-1,1,0,0,-1,1,-1,1};
int const N=2e5+5,M=1e2+1,Mod=1e9+7;
template <class t>struct segtree{
  const t ID=0;
  vector<t>seg;
  int n;
  void init(int _n){
    n=_n;
    seg.assign(n*2,ID);
  }
  t comp(t a,t b){return max(a,b);}
  void pull(int p){
    seg[p]=comp(seg[p*2],seg[p*2+1]);
  }
  void upd(int p,t val){
    seg[p+=n]=val;
    for(p/=2;p;p/=2)pull(p);
  }
  t qry(int l,int r){
    t ra=ID,rb=ID;
    for(l+=n,r+=n+1;l<r;l/=2,r/=2){
      if(l&1)ra=comp(ra,seg[l++]);
      if(r&1)rb=comp(rb,seg[--r]);
    }
    return comp(ra,rb);
  }
};
segtree<int>st;
pair<int,int>loc[N];
int a,b,c,d,freq[N];
vector<int>adj[N];
int nn;
void init(int n, vector<int> v) {
  int sz=(1<<((int)ceil(log2(n))))+1;
  nn=n;
  st.init(sz);
  for(int i=0;i<n;i++){
    st.upd(i+1,v[i]);
    freq[i]=v[i];
  }
  for(int i=0;i<n;i++){
    int x=v[i];
    int l=1,r=i+1,left=-1;
    while(l<=r){
      int m=(l+r)/2;
      if(st.qry(m,i+1)>x){
        left=m-1;
        l=m+1;
      }
      else {
        r=m-1;
      }
    }
    int right=-1;
    l=i+1,r=n;
    while(l<=r){
      int m=(l+r)/2;
      if(st.qry(i+1,m)>x){
        right=m-1;
        r=m-1;
      }
      else {
        l=m+1;
      }
    }
    if(left!=-1)
      left=freq[left];
    if(right!=-1)
      right=freq[right];
    loc[x]={left,right};
  }
  for(int i=1;i<=n;i++){
    if(loc[i].F!=-1)adj[i].pb(loc[i].F);
    if(loc[i].S!=-1)adj[i].pb(loc[i].S);
  }
}
int minimum_jumps(int A, int B, int C, int D) {
  a=A;b=B;c=C;d=D;
  queue<pair<int,int>>q;
  for(int i=a;i<=b;i++){
    q.push({freq[i],0});
  }
  int f[nn+1]={};
  for(int i=c;i<=d;i++)f[freq[i]]=1;
  bool vis[nn+1]={};
  while(q.size()){
    int u=q.front().F;
    int c=q.front().S;
    q.pop();
    vis[u]=1;
    if(f[u]){
      return c;
    }
    for(auto j:adj[u]){
      if(!vis[j])q.push({j,c+1});
    }
  }
  return -1;
}

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