Submission #1277100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277100		pvpro	Rainforest Jumps (APIO21_jumps)	C++20	0 / 100	4042 ms	27924 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> pup[LOG_N];

void init(int n, vector<int> a) {
    p = a;
    T.resize(n * 4);
    build(1, 0, n, a);
    binup[0].resize(n);
    pup[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()) {
            if (a[binup[0][i]] < a[st.back()]) {
                binup[0][i] = st.back();
            }
        }
        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()) {
            pup[0][i] = st.back();
            if (a[binup[0][i]] < a[st.back()]) {
                binup[0][i] = st.back();
            }
        } else {
            pup[0][i] = i;
        }
        st.pb(i);
    }
    for (int l = 1; l < LOG_N; ++l) {
        binup[l].resize(n);
        pup[l].resize(n);
        for (int i = 0; i < n; ++i) {
            binup[l][i] = binup[l-1][binup[l-1][i]];
            pup[l][i] = pup[l-1][pup[l-1][i]];
        }
    }
}

int getJumps(int a, int b) {
    int mx = get(1, 0, p.size(), a, b + 1);
    if (mx != p[b]) {
        return 1e9;
    }
    int ans = 0;
    for (int l = LOG_N - 1; l >= 0; --l) {
        if (p[binup[l][a]] < p[b]) {
            ans += (1<<l);
            a = binup[l][a];
        }
    }
    for (int l = LOG_N - 1; l >= 0; --l) {
        if (p[pup[l][a]] < p[b]) {
            ans += (1<<l);
            a = pup[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[binup[l][v]] < mx) {
            v = binup[l][v];
        }
    }
    if (v < a) {
        return -1;
    }
    int ans = 1e9;
    for (int j = c; j <= d; ++j) {
        ans = min(ans, getJumps(v, j));
    }
    if (binup[0][v] >= a) {
        for (int j = c; j <= d; ++j) {
            ans = min(ans, getJumps(binup[0][v], j));
        }
    }
    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: 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