Submission #1277107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277107		pvpro	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	600 ms	49268 KiB

jumps

#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
#include <complex>
#include <numeric>
#include <assert.h>
#include <functional>
#include <climits>
#include <cstring>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ushort = unsigned short;

#ifndef LOCAL
#define endl "\n"
#endif
#define f first
#define s second
#define vec vector
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
template<typename T1, typename T2>
istream& operator>> (istream &in, pair<T1, T2> &p) { in >> p.f >> p.s; return in; }
template<typename T1, typename T2>
ostream& operator<< (ostream &out, pair<T1, T2> p) { out << "(" << p.f << " " << p.s << ")"; return out; }
#define printv(v) cerr << #v << " "; for (auto &x : v) { cerr << x << " "; } cerr << endl;
#define printvv(v) cerr << #v << " "; for (auto &x : v) { for (auto &y : x) { cerr << y << " "; } cerr << endl; }
#define debug(x) cerr << #x << " " << x << endl;

template<typename T>
istream& operator>> (istream &in, vector<T> &v) {
    for (auto &x : v) {
        in >> x;
    }
    return in;
}
template<typename T>
ostream& operator<< (ostream &out, vector<T> v) {
    for (auto &x : v) {
        out << x << " ";
    }
    return out;
}
template<typename T>
void operator-=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x -= delta;
    }
}
template<typename T>
void operator+=(vector<T> &v, int delta) {
    for (auto &x : v) {
        x += delta;
    }
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

vector<int> T;

void build(int i, int l, int r, vector<int> &a) {
    if (l + 1 == r) {
        T[i] = a[l];
    } else {
        int m = (l + r) / 2;
        build(i * 2, l, m, a);
        build(i * 2 + 1, m, r, a);
        T[i] = max(T[i * 2], T[i * 2 + 1]);
    }
}

int get(int i, int l, int r, int ql, int qr) {
    if (l >= qr || r <= ql) {
        return 0;
    }
    if (ql <= l && r <= qr) {
        return T[i];
    } else {
        int m = (l + r) / 2;
        return max(get(i * 2, l, m, ql, qr), get(i * 2 + 1, m, r, ql, qr));
    }
}

vector<int> p;
const int LOG_N = 18;
vector<int> binup[LOG_N];
vector<int> R[LOG_N], L[LOG_N];

void init(int n, vector<int> a) {
    p = a;
    T.resize(n * 4);
    build(1, 0, n, a);
    binup[0].resize(n);
    L[0].resize(n);
    R[0].resize(n);
    iota(all(binup[0]), 0);
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.back()] < a[i]) {
            st.pop_back();
        }
        if (!st.empty()) {
            L[0][i] = st.back();
            if (a[binup[0][i]] < a[st.back()]) {
                binup[0][i] = st.back();
            }
        } else {
            L[0][i] = i;
        }
        st.pb(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && a[st.back()] < a[i]) {
            st.pop_back();
        }
        if (!st.empty()) {
            R[0][i] = st.back();
            if (a[binup[0][i]] < a[st.back()]) {
                binup[0][i] = st.back();
            }
        } else {
            R[0][i] = i;
        }
        st.pb(i);
    }
    for (int l = 1; l < LOG_N; ++l) {
        binup[l].resize(n);
        R[l].resize(n);
        L[l].resize(n);
        for (int i = 0; i < n; ++i) {
            binup[l][i] = binup[l-1][binup[l-1][i]];
            R[l][i] = R[l-1][R[l-1][i]];
            L[l][i] = L[l-1][L[l-1][i]];
        }
    }
}

int getJumps(int a, int L, int r) {
    int mx = get(1, 0, p.size(), a, L);
    int mxLR = get(1, 0, p.size(), L, r + 1);
    if (mx >= mxLR) {
        return 1e9;
    }
    if (p[a] >= mx) {
        if (p[a] <= mxLR) {
            return 1;
        }
    }
    int ans = 0;
    for (int l = LOG_N - 1; l >= 0; --l) {
        if (p[binup[l][a]] < mx) {
            ans += (1<<l);
            a = binup[l][a];
        }
    }
    if (p[binup[0][a]] >= mx) {
        if (p[binup[0][a]] <= mxLR) {
            return ans + 2;
        }
    }
    for (int l = LOG_N - 1; l >= 0; --l) {
        if (R[l][a] < L) {
            ans += (1<<l);
            a = R[l][a];
        }
    }
    return ans + 1;
}

int minimum_jumps(int a, int b, int c, int d) {
    int mx = get(1, 0, p.size(), b + 1, c);
    int v = b;
    for (int l = LOG_N - 1; l >= 0; --l) {
        if (p[L[l][v]] < mx && L[l][v] >= a) {
            v = L[l][v];
        }
    }
    int ans = 1e9;
    ans = min(ans, getJumps(v, c, d));
    if (L[0][v] >= a) {
        ans = min(ans, getJumps(L[0][v], c, d));
    }
    if (ans == 1e9) {
        ans = -1;
    }
    return ans;
}

#ifdef LOCAL
int main() {
    freopen("in.txt", "r", stdin);
    int N, Q;
    assert(2 == scanf("%d %d", &N, &Q));
    std::vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &H[i]));
    }
    init(N, H);

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

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