oj.uz

Submission #430411

# Submission time Handle Problem Language Result Execution time Memory
430411 2021-06-16T13:28:43 Z Supersonic Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 4000 ms 22412 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
int n;vector<int> v;
#define SIZE 131072
typedef long long ll;
vector<int> l;vector<int> r;vector<int> t;
int jm[1000001][21];
ll tree[2*SIZE];
int p2[21]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
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) {
  n=N;v=H;
  l.push_back(-1);t.push_back(0);
  for(int i=0;i<n;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<<endl;
  int p=20;
  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);
    return -1*1e8;
  }
  //cerr<<a<<' '<<p<<' '<<r[g(a,p)]<<endl;
  return p2[p]+mj(g(a,p),c,d);
}
int minimum_jumps(int a, int b, int c, int d) {
  int m1=-1,m1i=-1,m2=-1,m2i=-1;
  for(int i=c;i<=d;i++)if(v[i]>m2){m2=v[i];m2i=i;}
  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||m2i==-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);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1181 ms 18192 KB Output is correct
4 Execution timed out 4045 ms 22224 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 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 Correct 4 ms 200 KB Output is correct
6 Incorrect 3 ms 200 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 200 KB Output is correct
2 Correct 1 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 Correct 4 ms 200 KB Output is correct
6 Incorrect 3 ms 200 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 36 ms 17472 KB Output is correct
6 Correct 45 ms 21404 KB Output is correct
7 Correct 21 ms 11064 KB Output is correct
8 Correct 46 ms 21292 KB Output is correct
9 Correct 7 ms 3516 KB Output is correct
10 Correct 45 ms 21364 KB Output is correct
11 Correct 47 ms 22196 KB Output is correct
12 Correct 49 ms 22196 KB Output is correct
13 Incorrect 46 ms 22412 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 303 ms 10000 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 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Incorrect 303 ms 10000 KB Output isn't correct
5 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 1 ms 200 KB Output is correct
3 Correct 1181 ms 18192 KB Output is correct
4 Execution timed out 4045 ms 22224 KB Time limit exceeded
5 Halted 0 ms 0 KB -