oj.uz

Submission #430545

# Submission time Handle Problem Language Result Execution time Memory
430545 2021-06-16T15:37:41 Z Supersonic Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 2193 ms 26388 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);
    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:72:26: warning: unused variable 'm2i' [-Wunused-variable]
   72 |   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 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 426 ms 21392 KB Output is correct
4 Correct 2155 ms 26212 KB Output is correct
5 Correct 1525 ms 13368 KB Output is correct
6 Correct 2187 ms 26164 KB Output is correct
7 Correct 1628 ms 18736 KB Output is correct
8 Correct 2193 ms 26248 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 2 ms 328 KB Output is correct
6 Incorrect 3 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 2 ms 328 KB Output is correct
6 Incorrect 3 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 2 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 50 ms 20748 KB Output is correct
6 Correct 67 ms 25396 KB Output is correct
7 Correct 30 ms 13112 KB Output is correct
8 Correct 62 ms 25352 KB Output is correct
9 Correct 9 ms 4172 KB Output is correct
10 Correct 65 ms 25388 KB Output is correct
11 Correct 64 ms 26244 KB Output is correct
12 Correct 58 ms 26192 KB Output is correct
13 Incorrect 76 ms 26388 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 392 ms 11832 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 392 ms 11832 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 328 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 426 ms 21392 KB Output is correct
4 Correct 2155 ms 26212 KB Output is correct
5 Correct 1525 ms 13368 KB Output is correct
6 Correct 2187 ms 26164 KB Output is correct
7 Correct 1628 ms 18736 KB Output is correct
8 Correct 2193 ms 26248 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 2 ms 328 KB Output is correct
14 Incorrect 3 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -