oj.uz

Submission #528620

# Submission time Handle Problem Language Result Execution time Memory
528620 2022-02-20T21:11:40 Z DanerZein Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 16044 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int MAX_N=2e5+10;
const int MAX_P=MAX_N*4;
int st[MAX_P];
int val[MAX_N];
int dis[MAX_N];
int n;
vector<vi> G;
void init(int node,int a,int b){
  if(a==b){
    st[node]=val[a];
    return;
  }
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  init(le,a,mid);
  init(ri,mid+1,b);
  st[node]=max(st[le],st[ri]);
}
int query(int node,int a,int b,int l,int r){
  if(b<l || a>r) return 0;
  if(l<=a && r>=b) return st[node];
  int mid=(a+b)/2,le=2*node+1,ri=2*node+2;
  return max(query(le,a,mid,l,r),query(ri,mid+1,b,l,r));
}
int izquier(int x){
  int q=query(0,0,n-1,0,x);
  if(q==val[x]) return -1;
  int l=0,r=x;
  while(r-l>1){
    int mid=(l+r)/2;
    q=query(0,0,n-1,mid,r);
    if(q>val[x])
      l=mid;
    else r=mid;
  }
  return l;
}
int derecha(int x){
  int q=query(0,0,n-1,x,n-1);
  if(q==val[x]) return -1;
  int l=x,r=n-1;
  while(r-l>1){
    int mid=(l+r)/2;
    q=query(0,0,n-1,l,mid);
    if(q>val[x]) r=mid;
    else l=mid;
  }
  return r;
}
int ans[2010][2010];
bool iq[MAX_N];
void bfs(int u){
  for(int i=0;i<n;i++) {
    dis[i]=1e9;
    iq[i]=0;
  }
  dis[u]=0;
  iq[u]=1;
  queue<int> q;
  q.push(u);
  while(!q.empty()){
    int x=q.front();
    iq[x]=0;
    q.pop();
    for(auto &v:G[x]){
      if(dis[v]>dis[x]+1){
	dis[v]=dis[x]+1;
	if(!iq[v]){
	  q.push(v);
	  iq[v]=1;
	}
      }
    }
  }
}
void init(int N, std::vector<int> H) {
  for(int i=0;i<N;i++) val[i]=H[i];
  G.resize(N+1);
  n=N;
  init(0,0,n-1);
  for(int i=0;i<n;i++){
    int l=izquier(i);
    int r=derecha(i);
    // cout<<i<<": "<<l<<" "<<r<<endl;
    if(l!=-1) G[i].push_back(l);
    if(r!=-1) G[i].push_back(r);
  }
}
int minimum_jumps(int A, int B, int C, int D) {
  int ma=-1,id;
  int q=query(0,0,n-1,C,D);
  for(int i=A;i<=B;i++){
    if(ma<val[i] && val[i]<q){
      ma=val[i];
      id=i;
    }
  }
  if(ma==-1) return -1;
  int res=1e9;
  bfs(id);
  for(int j=C;j<=D;j++){
    res=min(res,dis[j]);
  }
  if(res>=1e9) res=-1;
  return res;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Execution timed out 4081 ms 13048 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 967 ms 13220 KB Output is correct
6 Correct 1211 ms 16044 KB Output is correct
7 Correct 567 ms 8148 KB Output is correct
8 Correct 1219 ms 15896 KB Output is correct
9 Correct 137 ms 2624 KB Output is correct
10 Correct 1244 ms 15852 KB Output is correct
11 Correct 640 ms 15792 KB Output is correct
12 Correct 1004 ms 15868 KB Output is correct
13 Correct 812 ms 15764 KB Output is correct
14 Correct 1205 ms 15936 KB Output is correct
15 Correct 1204 ms 15780 KB Output is correct
16 Correct 1190 ms 15820 KB Output is correct
17 Correct 1170 ms 16036 KB Output is correct
18 Correct 0 ms 200 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Incorrect 1 ms 200 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1210 ms 7480 KB Output is correct
5 Execution timed out 4077 ms 15916 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1210 ms 7480 KB Output is correct
5 Execution timed out 4077 ms 15916 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Execution timed out 4081 ms 13048 KB Time limit exceeded
4 Halted 0 ms 0 KB -