oj.uz

Submission #430551

# Submission time Handle Problem Language Result Execution time Memory
430551 2021-06-16T15:44:17 Z Supersonic Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2333 ms 26392 KB 
#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;
int n;vector<int> v;
#define SIZE 1048576
typedef long long ll;
vector<int> l;vector<int> r;vector<int> t;int y[1000001];
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++){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<<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);
    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;
  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;
  m2=q(c,d);
  int x=a-1;
  for (int e=p2[20];e>=1;e/=2) {
    while(q(x+e,b)>m2)x+=e;
  }
  x++;if(x>d)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:73:26: warning: unused variable 'm2i' [-Wunused-variable]
   73 |   int m1=-1,m1i=-1,m2=-1,m2i=-1;
      |                          ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 380 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 469 ms 21384 KB Output is correct
4 Correct 2333 ms 26168 KB Output is correct
5 Correct 1664 ms 13332 KB Output is correct
6 Correct 2154 ms 26260 KB Output is correct
7 Correct 1961 ms 18720 KB Output is correct
8 Correct 1897 ms 26260 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 2 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 2 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 49 ms 20820 KB Output is correct
6 Correct 59 ms 25348 KB Output is correct
7 Correct 28 ms 13112 KB Output is correct
8 Correct 64 ms 25396 KB Output is correct
9 Correct 11 ms 4176 KB Output is correct
10 Correct 74 ms 25328 KB Output is correct
11 Correct 72 ms 26128 KB Output is correct
12 Correct 68 ms 26200 KB Output is correct
13 Incorrect 62 ms 26392 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 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 509 ms 11780 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 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 509 ms 11780 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 380 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 469 ms 21384 KB Output is correct
4 Correct 2333 ms 26168 KB Output is correct
5 Correct 1664 ms 13332 KB Output is correct
6 Correct 2154 ms 26260 KB Output is correct
7 Correct 1961 ms 18720 KB Output is correct
8 Correct 1897 ms 26260 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 2 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -