Submission #742034

#	Time	Username	Problem	Language	Result	Execution time	Memory
742034		gagik_2007	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	1145 ms	41044 KiB

jumps

#include "jumps.h"
// all the includes you need here
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <bitset>
#include <deque>
#include <iomanip>
#include <numeric>
#include <functional>
#include <complex>
#include <random>
#include <chrono>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pld;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pdd> vpdd;
typedef vector<pld> vpld;
typedef vector<string> vs;
#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define rrep(i, a, b) for (int i = (b) - 1; i >= a; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define trav(a, x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define pq priority_queue
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl;
#define debug2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define debug3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define debug4(x, y, z, w) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << endl;
#define debug5(x, y, z, w, t) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << endl;
#define debug6(x, y, z, w, t, u) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << endl;
#define debug7(x, y, z, w, t, u, v) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << endl;
#define debug8(x, y, z, w, t, u, v, k) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << ", " << #k << " = " << k << endl;
#define debug9(x, y, z, w, t, u, v, k, l) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #w << " = " << w << ", " << #t << " = " << t << ", " << #u << " = " << u << ", " << #v << " = " << v << ", " << #k << " = " << k << ", " << #l << " = " << l << endl;

const int N = 2e5 + 7;
const int LG = 22;
ll n;
vii a;
int lft[N], rgt[N];
// high[i] = the index of max(lft[i], rgh[i]), low[i] = the index of min(lft[i], rgh[i])
int high[N], low[N];
// uph[i][j] = high[high[...[i]]] (2^j times), upl[i][j] = low[low[...[i]]] (2^j times)
int uph[N][LG], upl[N][LG];

// a function to find for each index i, the greatest index j such that j <= i and a[j] > a[i]
void find_left() {
    stack<int> st;
    rep(i, 0, n) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        if (st.empty()) {
            lft[i] = -1;
        } else {
            lft[i] = st.top();
        }
        st.push(i);
    }
}

// a function to find for each index i, the smallest index j such that j >= i and a[j] > a[i]
void find_right() {
    stack<int> st;
    rrep(i, 0, n) {
        while (!st.empty() && a[st.top()] <= a[i]) {
            st.pop();
        }
        if (st.empty()) {
            rgt[i] = n;
        } else {
            rgt[i] = st.top();
        }
        st.push(i);
    }
}

// a function to calculate the high and low arrays
void calc_high_low() {
    rep(i, 0, n) {
        if (lft[i] == -1 && rgt[i] == n) {
            high[i] = -1;
            low[i] = -1;
        } else if (lft[i] == -1) {
            high[i] = rgt[i];
            low[i] = rgt[i];
        } else if (rgt[i] == n) {
            high[i] = lft[i];
            low[i] = lft[i];
        } else {
            if (a[lft[i]] > a[rgt[i]]) {
                high[i] = lft[i];
                low[i] = rgt[i];
            } else {
                high[i] = rgt[i];
                low[i] = lft[i];
            }
        }
    }
}

// a function to calculate the sparse table for high and low
void calc_sparse() {
    rep(i, 0, n) {
        uph[i][0] = high[i];
        upl[i][0] = low[i];
    }
    rep(j, 1, LG) {
        rep(i, 0, n) {
            if (uph[i][j - 1] == -1) {
                uph[i][j] = -1;
            } else {
                uph[i][j] = uph[uph[i][j - 1]][j - 1];
            }
            if (upl[i][j - 1] == -1) {
                upl[i][j] = -1;
            } else {
                upl[i][j] = upl[upl[i][j - 1]][j - 1];
            }
        }
    }
}

// a function to go up from an index i by moving on the high array until we reach an index j such that a[j] > x
int go_up_high(int i, int x, int& cnt) {
    //cout<<"CALLED: "<<i<<" "<<x<<endl;
    if (i == -1) {
        return -1;
    }
    if (a[i] > x) {
        return -1;
    }
    if(a[i]==x){
        return i;
    }
    rrep(j, 0, LG - 1) {
        if (uph[i][j] == -1) {
            continue;
        }
        if (a[uph[i][j]] <= x) {
            i = uph[i][j];
            cnt += (1 << j);
        }
    }
    return i;
}

// a function to go up from an index i by moving on the low array until we reach an index j such that a[j] > x
int go_up_low(int i, int x, int& cnt) {
    if (i == -1) {
        return -1;
    }
    if (a[i] > x) {
        return -1;
    }
    if(a[i]==x){
        return i;
    }
    rrep(j, 0, LG - 1) {
        if (upl[i][j] == -1) {
            continue;
        }
        if (a[upl[i][j]] <= x) {
            i = upl[i][j];
            cnt += (1 << j);
        }
    }
    return i;
}

void init(int N, std::vector<int> H) {
    n = N;
    a = H;
    find_left();
    find_right();
    calc_high_low();
    calc_sparse();
}

int minimum_jumps(int A, int B, int C, int D) {
    if(A==B && C==D){
        if(B==C){
            return 0;
        }
        int cnt=0;
        int x = go_up_high(B, a[C], cnt);
        int y = go_up_low(x, a[C], cnt);
        // debug2(x, y);
        // debug(cnt);
        // for(int i=0;i<n;i++){
        //     debug6(i, a[i], lft[i], rgt[i], high[i], low[i]);
        // }
        // // debug the uph and upl arrays
        // rep(i, 0, n) {
        //     rep(j, 0, LG) {
        //         debug3(i, j, uph[i][j]);
        //     }
        // }
        if(a[y]==a[C]){
            return cnt;
        }
        return -1;
    }
    return -1;
}

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