#include<bits/stdc++.h>
using namespace std;
int lft[200007],rgt[200007],jmpl[200007][18],jmpg[200007][18];
bool czy1=1;
bool odw[200007];
int n;
vector<int>v;
void init(int N,vector<int>V){
n=N;
v=V;
while(v.size()<200007)
v.push_back(200006);
stack<int>s;
lft[200006]=200006;
rgt[200006]=200006;
//s.push(n);
for(int i=0;i<n;i++){
lft[i]=200006;
rgt[i]=200006;
}
//return;
for(int i=0;i<n;i++){
if(s.empty() || v[s.top()]>v[i])
s.push(i);
else{
rgt[s.top()]=i;
s.pop();
i--;
}
}
while(s.size()>0) s.pop();
for(int i=n-1;i>=0;i--){
if(s.empty() || v[s.top()]>v[i])
s.push(i);
else{
czy1=0;
lft[s.top()]=i;
s.pop();
i++;
}
}
for(int i=0;i<n;i++){
int pm=lft[i];
if(v[lft[i]]>v[rgt[i]]){
lft[i]=rgt[i];
rgt[i]=pm;
}
jmpg[i][0]=rgt[i];
jmpl[i][0]=lft[i];
}
jmpl[200006][0]=200006;
jmpg[200006][0]=200006;
for(int i=1;i<18;i++){
for(int j=0;j<n;j++){
jmpl[j][i]=jmpl[jmpl[j][i-1]][i-1];
jmpg[j][i]=jmpg[jmpg[j][i-1]][i-1];
cout<<jmpg[j][i]<<" ";
}
jmpl[200006][i]=200006;
jmpg[200006][i]=200006;
cout<<"\n";
}
for(int i=0;i<n;i++)
cout<<lft[i]<<" "<<rgt[i]<<"\n";
}
int minimum_jumps(int a,int b,int c,int d){
if(czy1)
return c-b;
if(a==b && c==d){
int ak=a;
int akindex=0;
int odp=0;
while(v[jmpg[a][akindex+1]]<=v[c])
akindex++;
odp+=1<<akindex;
//cout<<akindex<<" a ";
//return 0;
a=jmpg[a][akindex];
akindex--;
while(akindex>=0){
if(v[jmpg[a][akindex]]>v[c]){
akindex--;
continue;
}
odp+=1<<akindex;
a=jmpg[a][akindex];
akindex--;
//cout<<a<<" ";
}
akindex=0;
while(v[jmpl[a][akindex+1]]<=v[c])
akindex++;
odp+=1<<akindex;
//cout<<akindex<<" a ";
//return 0;
a=jmpl[a][akindex];
akindex--;
while(akindex>=0){
if(v[jmpl[a][akindex]]>v[c]){
akindex--;
continue;
}
odp+=1<<akindex;
a=jmpl[a][akindex];
akindex--;
//cout<<a<<" ";
}
if(a!=c)
odp=-1;
return odp;
}
odw[200006]=1;
int ans[n];
for(int i=0;i<n;i++){ odw[i]=0; ans[i]=200007;}
for(int i=a;i<=b;i++) odw[i]=1;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
for(int i=a;i<=b;i++){
pq.push({0,i});
}
while(!pq.empty()){
pair<int,int>pom=pq.top();
pq.pop();
ans[pom.second]=pom.first;
if(!odw[lft[pom.second]]){
odw[lft[pom.second]]=1;
pq.push({pom.first+1,lft[pom.second]});
}
if(!odw[rgt[pom.second]]){
odw[rgt[pom.second]]=1;
pq.push({pom.first+1,rgt[pom.second]});
}
//return 0;
}
int mn=200007;
for(int i=c;i<=d;i++){
mn=min(mn,ans[i]);
}
if(mn==200007)
mn=-1;
//cout<<ans[11];
return mn;
}
Compilation message
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:71:13: warning: unused variable 'ak' [-Wunused-variable]
71 | int ak=a;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7372 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7504 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7504 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7504 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7372 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7372 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
7372 KB |
Security Violation |
| 2 |
Halted |
0 ms |
0 KB |
- |
