Submission #1125923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125923		AverageAmogusEnjoyer	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4018 ms	22148 KiB

jumps

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

const int N=200200;
vector<int> radj[N];
vector<int> adjS[N];
int n;
bool special[N];
int l[N],r[N];
int dl[N],dr[N];
int out[N];
const int inf=1e9;
void init(int _N,vector<int> H) {
    int Max = 0;
    n=_N;
    for (int i=0;i<n;i++) if (cmax(Max,H[i]))
        special[i]=1;
    Max=0;
    for (int i=n-1;i>=0;i--) if (cmax(Max,H[i]))
        special[i]=1;
    vector<int> stk;
    for (int i=0;i<n;i++) {
        while(!stk.empty() && H[stk.back()] < H[i]) stk.pop_back();
        if (!stk.empty()) {
            if (special[i]) {
                assert(special[stk.back()]);
                adjS[i].push_back(stk.back());
            } else {
                radj[stk.back()].push_back(i);
                out[i]++;
            }
        }
        stk.push_back(i);
    }
    stk.clear();
    for (int i=n-1;i>=0;i--) {
        while(!stk.empty() && H[stk.back()] < H[i]) stk.pop_back();
        if (!stk.empty()) {
            if (special[i]) {
                assert(special[stk.back()]);
                adjS[i].push_back(stk.back());
            } else {
                radj[stk.back()].push_back(i);
                out[i]++;
            }
        }
        stk.push_back(i);
    }
    for (int i=0;i<n;i++) {
        l[i]=r[i]=(special[i]?i:-1);
        dl[i]=dr[i]=(special[i]?0:inf);
    }
    stk.clear();
    for (int i=0;i<n;i++) if (out[i]==0) {
        assert(special[i]);
        stk.push_back(i);
    }
    for (int i=0;i<stk.size();i++) {
        int u=stk[i];
        for (int &v: radj[u]) {
            if (special[u]) {
                if (v > u) {
                    l[v]=l[u];
                    dl[v]=1;
                } else {
                    r[v]=r[u];
                    dr[v]=1;
                }
            } else {
                l[v]=l[u],r[v]=r[u];
                cmin(dl[v],dl[u]+1),cmin(dr[v],dr[u]+1);
            }
            if (--out[v] == 0) {
                stk.push_back(v);
            }
        } 
    }
    // for (int i=0;i<n;i++) {
    //     cout << l[i] << " " << r[i] << " " << dl[i] << " " << dr[i] << endl;
    // }
}

int walk(int u,int c,int d) {
    if (u == -1) return inf;
    assert(special[u]);
    if (c <= u && u <= d) return 0;
    int ans = inf;
    for (int &v: adjS[u]) 
        cmin(ans,walk(v,c,d)+1);
    return ans;
}

int minimum_jumps(int a,int b,int c,int d) {
    int ans=inf;
    for (int i=a,j=a;i<=b;i=j) {
        int min1=inf,min2=inf;
        while(j<=b && dl[i]==dl[j]) {
            cmin(min1,dl[j]),cmin(min2,dr[j]);
            j++;
        }
        cmin(ans,min(min1+walk(l[i],c,d),min2+walk(r[i],c,d)));
    }
    return (ans==inf?-1:ans);
}

• 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