oj.uz

Submission #430348

# Submission time Handle Problem Language Result Execution time Memory
430348 2021-06-16T13:04:36 Z Supersonic Rainforest Jumps (APIO21_jumps) C++14
0 / 100
 1249 ms 22408 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)]>c))p--;
  if(p==-1)return -1*1e7;
  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 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Incorrect 1249 ms 18200 KB Output isn't correct
4 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 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Incorrect 4 ms 256 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 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Incorrect 4 ms 256 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 1 ms 256 KB Output is correct
5 Correct 47 ms 17536 KB Output is correct
6 Correct 60 ms 21300 KB Output is correct
7 Correct 28 ms 11064 KB Output is correct
8 Correct 57 ms 21412 KB Output is correct
9 Correct 10 ms 3420 KB Output is correct
10 Correct 50 ms 21316 KB Output is correct
11 Correct 56 ms 22224 KB Output is correct
12 Correct 50 ms 22184 KB Output is correct
13 Incorrect 50 ms 22408 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 Incorrect 377 ms 10004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.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 Incorrect 377 ms 10004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.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 Incorrect 1249 ms 18200 KB Output isn't correct
4 Halted 0 ms 0 KB -