Submission #798717

#	Time	Username	Problem	Language	Result	Execution time	Memory
798717		winter0101	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	3 ms	5020 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const int maxn=2e5+9;
int h[maxn];
int n;
pii a[maxn];
void buildstack(){
stack<int>t;
t.push(n+1);
for1(i,1,n){
while (!t.empty()&&h[t.top()]<h[i])t.pop();
a[i].fi=t.top();
t.push(i);
}
while (!t.empty())t.pop();
t.push(n+1);
for2(i,n,1){
while (!t.empty()&&h[t.top()]<h[i])t.pop();
a[i].se=t.top();
t.push(i);
}
}
vector<int>b[maxn];
int in[maxn],out[maxn],tme=0;
int pos[maxn],st[maxn*4];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void dfs(int u){
in[u]=++tme;
for (auto v:b[u]){
    dfs(v);
}
out[u]=tme;
}
int jump[maxn][21];
void init(int N,vector<int>H){
n=N;
for1(i,1,n)h[i]=H[i-1];
h[n+1]=n+1;
for1(i,1,n+1)pos[h[i]]=i;
for1(i,1,n)update(1,1,n,i,h[i]);
buildstack();
int root=-1;
for1(i,1,n){
if (a[i].fi==a[i].se&&a[i].se==n+1){
    root=i;
    continue;
}
if (h[a[i].fi]<h[a[i].se]){
b[a[i].fi].pb(i);
if (a[i].se!=n+1)jump[i][0]=a[i].se;
else jump[i][0]=a[i].fi;
//cout<<a[i].fi<<" "<<i<<'\n';
}
else {
b[a[i].se].pb(i);
if (a[i].fi!=n+1)jump[i][0]=a[i].fi;
else jump[i][0]=a[i].se;
//cout<<a[i].se<<" "<<i<<'\n';
}
}
for1(j,1,20){
for1(i,1,n){
jump[i][j]=jump[jump[i][j-1]][j-1];
}
}
dfs(root);
}
int minimum_jumps(int l1,int r1,int l2,int r2){
l1++,r1++,l2++,r2++;
if (a[l2].fi!=n+1&&a[l2].fi>=r1)return -1;
int vl=get(1,1,n,r1+1,l2-1);
if (vl>h[l2])return -1;
int u=pos[get(1,1,n,max(a[l2].fi+1,l1),r1)];
int ans=0;
for2(j,20,0){
if (jump[u][j]==0)continue;
int id=jump[u][j];
if (h[id]<=h[l2]){
    ans+=(1<<j);
    u=id;
}
}
if (h[u]<h[l2])return -1;
return ans;
}
/*signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.ANS","w",stdout);

}*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19