Submission #1111661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111661		RiverFlow	Rainforest Jumps (APIO21_jumps)	C++14	33 / 100	4065 ms	5052 KiB

jumps

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

int n, a[N], L[N], R[N];

void init(int N, vector<int> H) {
    n = N;
    FOR(i, 1, n) a[i] = H[i - 1];
    stack<int> st;
    FOR(i, 1, n) {
        while(sz(st) and a[st.top()]<=a[i])st.pop();
        L[i]=sz(st)?st.top():0;st.push(i);
    }
    while(st.size())st.pop();
    FOD(i, n, 1) {
        while(sz(st) and a[st.top()]<=a[i])st.pop();
        R[i]=sz(st)?st.top():0;st.push(i);
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int x = A, y = B, u = C, v = D;
    ++x, ++y, ++u, ++v;
    int mxx = 0;
    FOR(i, u, v) mxx = max(mxx, a[i]);
    int mx = 0;
    FOR(i, 1, u - 1) {
        if (a[i] > mxx) {
            mx = i;
        }
    }
    if (mx >= y) return -1;
    int luu=-1;
    x=max(x, mx+1);
    int cost=0;
    for(int j=x;j<=y;++j){
        if (R[j]>=u and R[j]<=v) return 1;
        if (L[j] and a[L[j]]<mxx){
            if (luu==-1 or a[luu]<a[L[j]])luu=L[j];
        }
        if (R[j] and a[R[j]]<mxx){
            if (luu==-1 or a[luu]<a[R[j]])luu=R[j];
        }
    }
    ++cost;
    while (true){
        if(R[luu]>=u and R[luu]<=v){
            ++cost;
            return cost;
        }
        ++cost;
        if(L[luu] and a[L[luu]]<mxx and a[L[luu]]>a[R[luu]]){
            luu=L[luu];
        }else
            luu=R[luu];
    }
    return cost;
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    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
/*     Let the river flows naturally     */

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