#include<bits/stdc++.h>
#define qc ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rt return
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vecin(a) for(auto &d:a)cin>>d;
typedef long long int ll;
const long long mod=1e9+7;
const int int_inf=2147483647;
const long long int ll_inf=9223372036854775807;
const int alp_up=64;
const int alp_lw=96;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
using namespace std;
ll gcd(ll a,ll b){if(b==0)rt a;rt gcd(b,a%b);}
ll lcm(ll a,ll b){rt a/gcd(a,b)*b;}
void setIO(string name)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
//*
int n;
vector<int>h;
vector<vector<int>>l,r,low,hgh;
void init(int N,vector<int>H)
{
n=N;h=H;
l.resize(20,vector<int>(n,-1));
r.resize(20,vector<int>(n,-1));
low.resize(20,vector<int>(n,-1));
hgh.resize(20,vector<int>(n,-1));
// monotonic stack for l and r
// -1 means no target
stack<int>s;
for(int i=0;i<n;i++)
{
while(!s.empty()&&h[s.top()]<h[i])s.pop();
if(!s.empty())l[0][i]=s.top();
s.push(i);
}
while(!s.empty())s.pop();
for(int i=n-1;i>=0;i--)
{
while(!s.empty()&&h[s.top()]<h[i])s.pop();
if(!s.empty())r[0][i]=s.top();
s.push(i);
}
// sparse table for l and r
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
if(l[i-1][j]!=-1)l[i][j]=l[i-1][l[i-1][j]];
if(r[i-1][j]!=-1)r[i][j]=r[i-1][r[i-1][j]];
}
}
// sparse table for low and hgh
// using dynamic programming
for(int i=0;i<n;i++){
if(l[0][i]==-1)hgh[0][i]=r[0][i];
else if(r[0][i]==-1)hgh[0][i]=l[0][i];
else if(h[l[0][i]]>h[r[0][i]]){
hgh[0][i]=l[0][i];
low[0][i]=r[0][i];
}
else{
hgh[0][i]=r[0][i];
low[0][i]=l[0][i];
}
}
for(int i=1;i<20;i++){
for(int j=0;j<n;j++){
if(low[i-1][j]!=-1)low[i][j]=low[i-1][low[i-1][j]];
if(hgh[i-1][j]!=-1)hgh[i][j]=hgh[i-1][hgh[i-1][j]];
}
}
//for(auto c:l)cout<<c<<" ";cout<<"\n";
//for(auto c:r)cout<<c<<" ";cout<<"\n";
//for(auto c:tall){for(auto d:c)cout<<d<<" ";cout<<"\n";}
}
int reachable(int cur,int c,int d,int lim,int ans) // #jump from cur
{
for(int i=19;i>=0;i--){
if(hgh[i][cur]==-1)continue;
if(h[hgh[i][cur]]>lim)continue;
if(hgh[i][cur]>=c)continue;
rt reachable(hgh[i][cur],c,d,lim,ans+(1<<i));
}
if(c<=hgh[0][cur]&&hgh[0][cur]<=d)rt ans+1;
for(int i=19;i>=0;i--){
if(low[i][cur]==-1)continue;
if(h[low[i][cur]]>lim)continue;
if(low[i][cur]>=c)continue;
rt reachable(low[i][cur],c,d,lim,ans+(1<<i));
}
if(c<=low[0][cur]&&low[0][cur]<=d)rt ans+1;
rt -1;
}
int tallest(int a,int cur,int lim) // tallest tree in [a,cur] not higher than lim
{
for(int i=19;i>=0;i--){
if(l[i][cur]==-1)continue;
if(h[l[i][cur]]>lim)continue;
if(l[i][cur]<a)continue;
rt tallest(a,l[i][cur],lim);
}
rt cur;
}
int minimum_jumps(int a,int b,int c,int d)
{
int t_dest=tallest(c,d,n);
int t_strt=tallest(a,b,h[t_dest]);
rt reachable(t_strt,c,d,t_dest,0);
}
int xmain()
{
init(7, {3, 2, 1, 6, 4, 5, 7});
cout<<minimum_jumps(4, 4, 6, 6)<<" "<<minimum_jumps(1, 3, 5, 6)<<" "<<minimum_jumps(0, 1, 2, 2);
rt 0;
}
/*/
vector<int> construct_permutation(ll k)
{
k-=2;
vector<int>ans;
for(int i=k;i>=0;i--){
ans.push_back(i);
}
rt ans;
}
int smain()
{
}
//*/
Compilation message
jumps.cpp: In function 'void setIO(std::string)':
jumps.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
24 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
25 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
171 ms |
52636 KB |
Output is correct |
4 |
Correct |
1004 ms |
66060 KB |
Output is correct |
5 |
Correct |
1029 ms |
33424 KB |
Output is correct |
6 |
Correct |
1189 ms |
66152 KB |
Output is correct |
7 |
Correct |
718 ms |
45272 KB |
Output is correct |
8 |
Correct |
995 ms |
66232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
208 KB |
Output is correct |
5 |
Incorrect |
57 ms |
53248 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Incorrect |
210 ms |
30432 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
0 ms |
208 KB |
Output is correct |
4 |
Incorrect |
210 ms |
30432 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
171 ms |
52636 KB |
Output is correct |
4 |
Correct |
1004 ms |
66060 KB |
Output is correct |
5 |
Correct |
1029 ms |
33424 KB |
Output is correct |
6 |
Correct |
1189 ms |
66152 KB |
Output is correct |
7 |
Correct |
718 ms |
45272 KB |
Output is correct |
8 |
Correct |
995 ms |
66232 KB |
Output is correct |
9 |
Correct |
1 ms |
208 KB |
Output is correct |
10 |
Correct |
1 ms |
208 KB |
Output is correct |
11 |
Correct |
0 ms |
208 KB |
Output is correct |
12 |
Correct |
0 ms |
208 KB |
Output is correct |
13 |
Incorrect |
2 ms |
208 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |