Submission #668325

#	Time	Username	Problem	Language	Result	Execution time	Memory
668325		Minhho	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	1049 ms	34876 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], seg[2*maxn], hi[20][maxn], l[20][maxn], r[20][maxn], n, q;

inline int qry(int lx, int rx)
{
    int ans = 0;
    for (lx+=n, rx+=n+1; lx<rx; lx>>=1, rx>>=1)
    {
        if (lx & 1) ans = max(ans, seg[lx++]);
        if (rx & 1) ans = max(ans, seg[--rx]);
    }
    return ans;
}

void init(int N, vector<int> H)
{
    n = N;
    for (int i=1; i<=n; i++) a[i] = H[i-1], seg[n+i] = a[i];
    for (int i=n; i>=1; i--) seg[i] = max(seg[i<<1], seg[i<<1|1]);
    vector<int> dq;
    for (int i=n; i>=1; i--)
    {
        while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
        r[0][i] = dq.size() ? dq.back() : -1;
        dq.emplace_back(i);
    }
    dq.clear();
    for (int i=1; i<=n; i++)
    {
        while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
        l[0][i] = dq.size() ? dq.back() : -1;
        dq.emplace_back(i);
    }
//    for (int i=1; i<=n; i++) hi[0][i] = (r[0][i] != -1 && (l[0][i] == -1 || a[r[0][i]] >= a[l[0][i]]) ? r[0][i] : l[0][i]);
//    for (int i=1; i<=n; i++) cerr<<i<<" "<<l[0][i]<<" "<<r[0][i]<<"\n";
    for (int i=1; i<=18; i++)
        for (int j=1; j<=n; j++)
            r[i][j] = (r[i-1][j] != -1 ? r[i-1][r[i-1][j]] : -1),
            l[i][j] = (l[i-1][j] != -1 ? l[i-1][l[i-1][j]] : -1);//, cerr<<"SPT: "<<i<<" "<<j<<" "<<r[i][j]<<"\n";
//            hi[i][j] = hi[i-1][hi[i-1][j]];
}

int minimum_jumps(int A, int B, int C, int D)
{
    int ls, rs, le, re;
//    cin>>ls>>rs>>le>>re;
    ls = A, rs = B, le = C, re = D;
    ls++, rs++, le++, re++;
    if (qry(rs, le-1) > qry(le, re)) return -1;
    int cur = rs, mx = qry(le, re), ans = 0;
    for (int i=18; i>=0; i--)
        if (l[i][cur] != -1 && l[i][cur] >= ls && a[l[i][cur]] < mx) cur = l[i][cur];
    for (int i=18; i>=0; i--)
        if (r[i][cur] != -1 && r[i][cur] < le) ans += (1<<i), cur = r[i][cur];
    return ans + 1;
}

//int main()
//{
//
//}

• Subtask 1: 4 / 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