Submission #520787

#	Time	Username	Problem	Language	Result	Execution time	Memory
520787		lohacho	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1461 ms	63844 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

struct Seg{
    int n;
    vector<int> tree;
    Seg(int N):n(N){
        tree.resize(n * 4);
    }
    void add(int x, int l, int r, int val){
        tree[x] = val;
    }
    void push(int x, int l, int r, int pl, int pr, int val){
        if(pr < l || pl > r || pl > pr) return;
        if(l >= pl && r <= pr){
            add(x, l, r, val);
            return;
        }
        int mid = (l + r) >> 1;
        push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
        tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
    }
    int get(int x, int l, int r, int fl, int fr){
        if(fr < l || fl > r || fl > fr) return -1;
        if(l >= fl && r <= fr) return tree[x];
        int mid = (l + r) >> 1;
        return max(get(x * 2, l, mid, fl, fr), get(x * 2 + 1, mid + 1, r, fl, fr));
    }
};

const int NS = (int)2e5 + 4;
int l[NS][24], r[NS][24], lr[NS][24], n;
Seg tree(NS);
vector<int> h;

void init(int N, std::vector<int> H) {
    n = N;
    h.push_back((int)1e9);
    for(int i = 0; i < n; ++i){
        h.push_back(H[i]);
    }
    h.push_back((int)1e9);
    for(int i = 1; i <= n; ++i){
        tree.push(1, 1, n, i, i, h[i]);
    }
    vector<pair<int, int>> stk = {{h[0], 0}};
    for(int i = 1; i <= n; ++i){
        while(stk.back().first < h[i]){
            stk.pop_back();
        }
        l[i][0] = stk.back().second;
        stk.push_back({h[i], i});
    }
    stk = {{h[n + 1], n + 1}};
    for(int i = n; i >= 1; --i){
        while(stk.back().first < h[i]){
            stk.pop_back();
        }
        r[i][0] = stk.back().second;
        stk.push_back({h[i], i});
    }
    for(int i = 1; i <= n; ++i){
        lr[i][0] = (h[l[i][0]] > h[r[i][0]] ? l[i][0] : r[i][0]);
    }
    for(int j = 1; j < 20; ++j){
        for(int i = 1; i <= n; ++i){
            l[i][j] = l[l[i][j - 1]][j - 1];
            r[i][j] = r[r[i][j - 1]][j - 1];
            lr[i][j] = lr[lr[i][j - 1]][j - 1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    ++A, ++B, ++C, ++D;
    int mh = tree.get(1, 1, n, B + 1, C - 1), rh = tree.get(1, 1, n, C, D);
    int pos = B;
    for(int i = 19; i >= 0; --i){
        if(l[pos][i] >= A && h[l[pos][i]] < rh){
            pos = l[pos][i];
        }
    }
    int rv = 0;
    for(int i = 19; i >= 0; --i){
        if(h[pos] < mh && h[lr[pos][i]] < mh){
            pos = lr[pos][i]; rv += (1 << i);
        }
    }
    if(h[pos] < mh && h[lr[pos][0]] < rh){
        pos = lr[pos][0], ++rv;
    }
    if(h[pos] > rh || mh > rh) return -1;
    if(h[pos] > mh) return rv + 1;
    for(int i = 19; i >= 0; --i){
        if(r[pos][i] < C && r[pos][i]){
            pos = r[pos][i]; rv += (1 << i);
        }
    }
    return rv + 1;
}

• 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