Submission #872033

#	Time	Username	Problem	Language	Result	Execution time	Memory
872033		vjudge1	Rainforest Jumps (APIO21_jumps)	C++11	4 / 100	709 ms	47220 KiB

jumps

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

#define MAX 212345

//int _n, _q;
//vector<int> _h;

vector<int> h;
int up_r[MAX][21], up_l[MAX][21];

int build_r(int pos) {
    int nxt = pos + 1;
    while (nxt < h.size() && h[pos] > h[nxt]) nxt = build_r(nxt);
    if (nxt == h.size()) up_r[pos][0] = pos;
    else up_r[pos][0] = nxt;
    return nxt;
}

int build_l(int pos) {
    int nxt = pos - 1;
    while (nxt >= 0 && h[pos] > h[nxt]) nxt = build_l(nxt);
    if (nxt == -1) up_l[pos][0] = pos;
    else up_l[pos][0] = nxt;
    return nxt;
}

void init(int N, vector<int> H) {
    for (int i = 0; i < N; i++) h.push_back(H[i]);
    memset(up_r, -1, sizeof up_r); memset(up_l, -1, sizeof up_l);
    for (int i = 0; i < N; i++) {
        if (up_r[i][0] == -1) build_r(i);
        if (up_l[N - i - 1][0] == -1) build_l(N - i - 1);
    }
    int l = ceil(log2(N));
    for (int j = 1; j <= l; j++)
        for (int i = 0; i < N; i++) {
            up_r[i][j] = up_r[up_r[i][j-1]][j-1];
            up_l[i][j] = up_l[up_l[i][j-1]][j-1];
        }
}

int minimum_jumps(int A, int B, int C, int D) {
    if (C == B + 1) {
        if (up_r[B][0] > B && up_r[B][0] <= C) { 
            //printf("1\n"); 
            return 1; }
        else { 
            //printf("-1\n"); 
            return -1;}
    }

    int mid = B + 1;
    for (int l = ceil(log2(C - 1 - mid + 1)); l >= 0; l--) { if (up_r[mid][l] < C) mid = up_r[mid][l]; }

    int b = B;
    for (int l = ceil(log2(B - A + 1)); l >= 0; l--) { if (up_l[b][l] >= A && h[up_l[b][l]] < h[mid]) b = up_l[b][l]; }

    int ans = -1;

    if (h[B] < h[mid]) {
        int tmp_ans = 0, _b = b;
        for (int l = ceil(log2(D - _b + 1)); l >= 0; l--) { if (up_r[_b][l] < C) { _b = up_r[_b][l]; tmp_ans += 1 << l; } }
        if (up_r[_b][0] <= D) {
            tmp_ans++;
            ans = tmp_ans;
        }
    }

    if (h[B] >= h[mid]) {
        if (up_r[B][0] <= D) ans = 1;
    }
    else if (up_l[b][0] >= A && h[up_l[b][0]] >= h[mid]) {
        b = up_l[b][0];
        if (up_r[b][0] <= D) ans = 1;
    }

    //printf("%d\n", ans);
    return ans; 

    
    /*
    int ans = 1123456789;    
    
    int b = B;
    for (int l = ceil(log2(B - A + 1)); l >= 0; l--) { if (up_l[b][l] >= A && h[up_l[b][l]] < h[mid]) b = up_l[b][l]; }
    
    if (h[b] < h[mid]) {
        ans = 0; int _b = b;
        for (int l = ceil(log2(D - b + 1)); l >= 0; l--) { if (up_r[_b][l] < C) { _b = up_r[_b][l]; ans += 1 << l; } }
        ans = up_r[b][0] <= D ? ans + 1 : 1123456789;
    }

    if (h[b] >= h[mid] || up_l[b][0] >= A) {
        int tmp_ans = 0;
        b = h[b] <= h[mid] ? up_l[b][0] : b;
        for (int l = ceil(log2(D - b + 1)); l >= 0; l--) { if (up_r[b][l] < C) { b = up_r[b][l]; ans += 1 << l; } } 
        tmp_ans = up_r[b][0] <= D ? tmp_ans + 1 : 1123456789;
        ans = min(ans, tmp_ans);
    }

    //printf("%d\n", ans);
    return ans == 1123456789 ? -1 : ans; */
}

/*
int main() {
    
    scanf("%d %d", &_n, &_q);
    for (int i = 0, tmp = -1; i < _n; i++) { scanf("%d", &tmp); _h.push_back(tmp); }
    init(_n, _h);
    for (int i = 0; i < _q; i++) {
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
        minimum_jumps(a, b, c, d);
    }
    //for (int i = 0; i < _n; i++) printf("%d ", up_l[i][0]);
    //printf("\n");
    //for (int i = 0; i < _n; i++) printf("%d ", up_r[i][0]);
    //printf("\n");    
} */

Compilation message (stderr)

jumps.cpp: In function 'int build_r(int)':
jumps.cpp:14:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     while (nxt < h.size() && h[pos] > h[nxt]) nxt = build_r(nxt);
      |            ~~~~^~~~~~~~~~
jumps.cpp:15:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (nxt == h.size()) up_r[pos][0] = pos;
      |         ~~~~^~~~~~~~~~~

• 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