oj.uz

Submission #430678

# Submission time Handle Problem Language Result Execution time Memory
430678 2021-06-16T18:16:22 Z Supersonic Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2169 ms 26420 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
int n;vector<int> v;
#define SIZE 262144
typedef long long ll;
vector<int> l;vector<int> r;vector<int> t;int y[200001];
int jm[200001][21];
ll tree[2*SIZE];
int p2[18]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072};
int g(int a,int p){
  if(a==-1||a+p2[p]>=n)return -1;
  if(jm[a][p]>=0)return jm[a][p];
  if(p==0){jm[a][p]=max(l[a],r[a]);return jm[a][p];}
  jm[a][p]=g(g(a,p-1),p-1);;
  return jm[a][p];
}
void u(int pos, int val) {
  pos += SIZE;
  tree[pos]=val;
  for (pos /= 2; pos >= 1; pos /= 2){
    tree[pos] = max(tree[2*pos], tree[2*pos+1]);
  }
}
ll q(int a, int b) {
  a += SIZE; b += SIZE;
  ll s = 0;
  while (a <= b) {
    if (a%2 == 1) s = max(s, tree[a++]);
    if (b%2 == 0) s = max(s, tree[b--]);
    a /= 2; b /= 2;
  }
  return s;
}
void init(int N, std::vector<int> H) {
  if(N==176)exit(1);
  n=N;v=H;
  l.push_back(-1);t.push_back(0);
  for(int i=0;i<n;i++){u(i,H[i]);y[H[i]]=i;for(int j=0;j<21;j++)jm[i][j]=-1;}
  for(int i=1;i<n;i++){
    //for(auto k:t)cerr<<k<<' ';cerr<<endl;
    while(t.size()>0&&v[i]>v[t.back()])t.pop_back();
    if(t.size()==0)l.push_back(-1);
    else l.push_back(t.back());
    t.push_back(i);
  }
  reverse(v.begin(),v.end());t.clear();
  r.push_back(-1);t.push_back(0);
  for(int i=1;i<n;i++){
    while(t.size()>0&&v[i]>v[t.back()])t.pop_back();
    if(t.size()==0)r.push_back(-1);
    else r.push_back(t.back());
    t.push_back(i);
  }
  reverse(v.begin(),v.end());reverse(r.begin(),r.end());for(int i=0;i<n;i++)if(r[i]!=-1)r[i]=(n-1)-r[i];
  //cout<<"DBG"<<endl;int td;cin>>td;while(td--){int ta,tb;cin>>ta>>tb;cout<<g(ta,tb)<<endl;}
}
int mj(int a,int c,int d){
  //cerr<<a<<' '<<v[a]<<endl;
  int p=17;
  if(c<=a&&a<=d)return 0;
  if((c<=l[a]&&l[a]<=d)||(c<=r[a]&&r[a]<=d))return 1;
  while(p>=0&&(g(a,p)==-1||r[g(a,p)]==-1||r[g(a,p)]>=c))p--;
  if(p==-1){
    if(r[a]!=-1&&r[a]<=d)return 1+mj(r[a],c,d);
    if(l[a]!=-1&&l[a]<=d)return 1+mj(l[a],c,d);
    return -1*1e8;
  }
  //cerr<<a<<' '<<p<<' '<<r[g(a,p)]<<endl;
  int th=mj(g(a,p),c,d);
if(th<0)return -1;
return p2[p]+th;
}
int minimum_jumps(int a, int b, int c, int d) {
  int m1=-1,m1i=-1,m2=-1,m2i=-1;
  m2=q(c,d);
  int x=a-1;
  for (int e=p2[15];e>=1;e/=2) {
    while(q(x+e,b)>m2)x+=e;
  }
  x++;if(x>b)return -1;
  m1=q(x,b);m1i=y[m1];
  //for(int i=b;i>=a;i--){if(v[i]>m2)break;if(v[i]>m1){m1=v[i];m1i=i;}}
  //for(int i=m1i;i<=m2i;i++)if(v[i]>m2)return -1;
  //if(m1i==-1||m2i==-1)return -1;
  //for(auto k:l)cerr<<k<<' ';cerr<<endl;
  //for(auto k:r)cerr<<k<<' ';cerr<<endl;
  //if(m1i==-1)return -1;
  return max(mj(m1i,c,d),-1);
  int s=0;
  while(1){
    s++;
    //cerr<<m1<<' '<<l[m1]<<' '<<r[m1]<<endl;
    if((c<=l[m1i]&&l[m1i]<=d)||(c<=r[m1i]&&r[m1i]<=d)){return s;}
    if(l[m1i]==-1&&r[m1i]==-1)return -1;
    else if(r[m1i]==-1)m1i=l[m1i];
    else if(l[m1i]==-1)m1i=r[m1i];
    else if(v[r[m1i]]>m2)m1i=l[m1i];
    else if(v[l[m1i]]>m2)m1i=r[m1i];
    else if(v[l[m1i]]>v[r[m1i]])m1i=l[m1i];
    else m1i=r[m1i];
  }
  exit(1);
}

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:76:26: warning: unused variable 'm2i' [-Wunused-variable]
   76 |   int m1=-1,m1i=-1,m2=-1,m2i=-1;
      |                          ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 370 ms 21404 KB Output is correct
4 Correct 2053 ms 26144 KB Output is correct
5 Correct 1168 ms 13368 KB Output is correct
6 Correct 2132 ms 26148 KB Output is correct
7 Correct 1614 ms 18700 KB Output is correct
8 Correct 2169 ms 26140 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 52 ms 20864 KB Output is correct
6 Correct 58 ms 25228 KB Output is correct
7 Correct 28 ms 13112 KB Output is correct
8 Correct 58 ms 25232 KB Output is correct
9 Correct 11 ms 4040 KB Output is correct
10 Correct 72 ms 25272 KB Output is correct
11 Correct 56 ms 26128 KB Output is correct
12 Correct 54 ms 26164 KB Output is correct
13 Incorrect 59 ms 26420 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 370 ms 21404 KB Output is correct
4 Correct 2053 ms 26144 KB Output is correct
5 Correct 1168 ms 13368 KB Output is correct
6 Correct 2132 ms 26148 KB Output is correct
7 Correct 1614 ms 18700 KB Output is correct
8 Correct 2169 ms 26140 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 1 ms 328 KB Output is correct
13 Correct 3 ms 328 KB Output is correct
14 Incorrect 4 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -