Submission #1112680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112680		RiverFlow	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	2501 ms	60844 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;

const int LG=17;

int n, a[N], L[N][LG+1], R[N][LG+1];
int sp[N][LG+1], d[N][LG+1], lg[N];
int get(int l, int r){
    int j=lg[r-l+1];
    return min(d[l][j], d[r-(1<<j)+1][j]);
}
void init(int N, vector<int> H) {
    n = N;
    FOR(i, 1, n) a[i] = H[i - 1];
    FOR(i, 2, n) lg[i]=lg[i/2]+1;
    stack<int> st;
    FOR(i, 1, n) {
        while(sz(st) and a[st.top()]<=a[i])st.pop();
        L[i][0]=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][0]=sz(st)?st.top():0;st.push(i);
    }
    FOR(i, 1, n) {
        d[i][0]=a[i];
    }
    FOR(i, 1, n) {
        if (L[i][0]==0 and R[i][0]==0){
            sp[i][0]=-1;
        } else {
            sp[i][0]=(a[L[i][0]]>a[R[i][0]]?L[i][0]:R[i][0]);
        }
    }
    FOR(j, 1, LG)
    FOR(i, 1, n) {
        if(i+(1<<j)-1<=n)
            d[i][j]=min(d[i][j-1], d[i+(1<<(j-1))][j-1]);
        L[i][j]=L[L[i][j-1]][j-1];
        R[i][j]=R[R[i][j-1]][j-1];
        if (sp[i][j-1]==-1)
            sp[i][j]=-1;
        else
            sp[i][j]=sp[sp[i][j-1]][j-1];
    }
}

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 MIN=get(u,v);
    int mx = u;
    FOD(j, LG, 0) if (R[mx][j] > 0 and R[mx][j] <= v) {
        mx = R[mx][j];
    }
    if (a[y]>a[mx])return -1;
    FOD(j, LG, 0) if (L[y][j] > 0 and L[y][j]>=x and a[L[y][j]]<a[mx]) {
        y=L[y][j];
    }
    bool ok = 0;
    int tmp=y;
    FOD(j, LG, 0) if (R[y][j]>0 and R[y][j]<=v) y=R[y][j];
    if (y<u) return -1;
    y=tmp;
    int res=0;
    //nhay be hon a[min]
    FOD(j, LG, 0) if (sp[y][j]!=-1 and R[sp[y][j]][0]>0 and R[sp[y][j]][0]<u) {
        res+=(1<<j);
        y=sp[y][j];
    }
//    cerr << "y:" << y << nl;
    if (R[y][0]>=u and R[y][0]<=v)
        return res+1;
    if (a[L[y][0]]>a[R[y][0]] and a[L[y][0]]<a[mx]){
        ++res;
        y=L[y][0];
    }
    //luc nay thi trai dang chan roi
    FOD(j, LG, 0) if (R[y][j]>0 and R[y][j]<u){
        res+=(1<<j);
        y=R[y][j];
    }
    return res+1;
}

#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     */

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:79:9: warning: unused variable 'MIN' [-Wunused-variable]
   79 |     int MIN=get(u,v);
      |         ^~~
jumps.cpp:88:10: warning: unused variable 'ok' [-Wunused-variable]
   88 |     bool ok = 0;
      |          ^~

• 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