oj.uz

Submission #561632

# Submission time Handle Problem Language Result Execution time Memory
561632 2022-05-13T09:23:34 Z Omar_Elgedawy Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 218740 KB 
#include <bits/stdc++.h>
// #include "jumb.cpp"
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(ra,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];
    // cout<<left<<' '<<right<<el;
    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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Execution timed out 4006 ms 16668 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Incorrect 6 ms 4944 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 5 ms 4944 KB Output is correct
6 Incorrect 6 ms 4944 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 4 ms 4944 KB Output is correct
4 Correct 4 ms 4944 KB Output is correct
5 Execution timed out 4030 ms 150784 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Execution timed out 4061 ms 218740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Execution timed out 4061 ms 218740 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Execution timed out 4006 ms 16668 KB Time limit exceeded
4 Halted 0 ms 0 KB -