Submission #798768

#	Time	Username	Problem	Language	Result	Execution time	Memory
798768		winter0101	Rainforest Jumps (APIO21_jumps)	C++14	16 / 100	1207 ms	62692 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];
int dep[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]){
    dep[v]=dep[u]+1;
    dfs(v);
}
out[u]=tme;
}
int jump[maxn][21],mx[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];
}
}
for1(i,1,n)mx[i][0]=h[i];
for1(j,1,20){
for1(i,1,n){
if (i+(1<<j)-1>n)continue;
mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
}
dfs(root);
}
int jumps(int l1,int r1,int l2,int r2){
//cerr<<a[l2].fi<<'\n';
if (a[l2].fi!=n+1&&a[l2].fi>=r1)return -1;
int vl=get(1,1,n,r1+1,l2-1);
//cerr<<vl<<'\n';
if (vl>h[l2])return -1;
int hihihaha=a[l2].fi+1;
if (hihihaha==n+2)hihihaha=l1;
int u=pos[get(1,1,n,max(hihihaha,l1),r1)];
//cerr<<u<<'\n';
int ans=0;
for2(j,20,0){
if (jump[u][j]==0)continue;
int id=jump[u][j];
if (h[id]<=h[l2]){
    //cerr<<id<<" "<<j<<'\n';
    ans+=(1<<j);
    u=id;
}
}
ans+=dep[u]-dep[l2];
return ans;
}
int minimum_jumps(int l1,int r1,int l2,int r2){
l1++,r1++,l2++,r2++;
//cerr<<a[l2].fi<<'\n';
if (get(1,1,n,l2,r2)<get(1,1,n,r1,l2-1))return -1;
int vl=get(1,1,n,r1+1,l2-1);
//cerr<<vl<<'\n';
if (vl>get(1,1,n,l2,r2))return -1;
//cerr<<"jkjk"<<'\n';
int pp=l2;
for2(i,20,0){
if (mx[pp][i]==0)continue;
if (pp+(1<<i)>r2)continue;
if (mx[pp+1][i]<=vl){
    pp=pp+(1<<i);
    //cerr<<pp<<'\n';
}
}
//cerr<<pp<<" "<<h[pp]<<'\n';
if (h[pp+1]<=vl)return -1;
if (h[pp]<=vl)pp++;
//cerr<<pp<<'\n';
if (a[pp].fi<=r1&&a[pp].fi>=l1){
    int id=a[pp].fi;
    if (h[id]>get(1,1,n,l2,r2)){
        return jumps(id,r1,pp,pp);
    }
    return 1;
}
int u=pos[get(1,1,n,l1,r1)];
int ans=0;
for2(j,20,0){
if (jump[u][j]==0)continue;
int id=jump[u][j];
if (h[id]<=h[pp]){
    //cerr<<id<<" "<<j<<'\n';
    ans+=(1<<j);
    u=id;
}
}
int mn=ans+dep[u]-dep[pp];
int nxt=jump[u][0];
if (nxt!=0&&nxt!=n+1&&a[nxt].se<=r2)mn=min(mn,ans+1+1);
return mn;
}
/*signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int N, Q;
    scanf("%d %d", &N, &Q);
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d", &H[i]);
  }
  init(N, H);

  for (int i = 0; i < Q; ++i) {
    int A, B, C, D;
    scanf("%d %d %d %d", &A, &B, &C, &D);
    printf("%d\n", minimum_jumps(A, B, C, D));
  }
  return 0;
}*/

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