Submission #1178019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178019		KasymK	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4094 ms	5084 KiB

jumps

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 2e5+5;
const int INF = 1e9;
int v[N], l[N], r[N], dis[N], n;

void init(int N, vector<int> A){
    int op=0;
    tr(it, A)
    v[++op]=*it;
    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    n=N;
    stack<int> st;
    for(int i = 1; i <= n; ++i){
        while(!st.empty() and v[st.top()]<v[i])
            st.pop();
        if(!st.empty())
            l[i]=st.top();
        st.push(i);
    }
    while(!st.empty())
        st.pop();
    for(int i = n; i >= 1; --i){
        while(!st.empty() and v[st.top()]<v[i])
            st.pop();
        if(!st.empty())
            r[i]=st.top();
        st.push(i);
    }
}

int minimum_jumps(int a, int b, int c, int d){
    a++, b++, c++, d++;
    queue<int> q;
    for(int i = 1; i <= n; ++i){
        dis[i]=INF;
        if(i>=a and i<=b)
            q.push(i), dis[i]=0;
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(~l[x] and umin(dis[l[x]], dis[x]+1))
            q.push(l[x]);
        if(~r[x] and umin(dis[r[x]], dis[x]+1))
            q.push(r[x]);
    }
    int answer=INF;
    for(int i = c; i <= d; ++i)
        umin(answer, dis[i]);
    if(answer==INF)
        return -1;
    return answer;
}

// int main(){
//     int n;
//     scanf("%d", &n);
//     vector<int> v;
//     for(int i = 1; i <= n; ++i){
//         int x;
//         scanf("%d", &x);
//         v.pb(x);
//     }
//     init(n, v);
//     int q;
//     scanf("%d", &q);
//     while(q--){
//         int a, b, c, d;
//         scanf("%d%d%d%d", &a, &b, &c, &d);
//         printf("%d\n", minimum_jumps(a, b, c, d));
//     }
//     return 0;
// }

• 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