Submission #613722

#	Time	Username	Problem	Language	Result	Execution time	Memory
613722		AugustinasJucas	Rainforest Jumps (APIO21_jumps)	C++14	0 / 100	260 ms	25564 KiB

jumps

#include "jumps.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> mas;
const int dydis = 1e5 + 10;
const int dd = 20;
int mx[dydis][dd];
int lg2[dydis];
void build() {
    lg2[1] = 0;
    for(int i = 2; i < dydis; i++) lg2[i] = lg2[i/2] + 1;
    for(int i = 0; i < n; i++) {
        mx[i][0] = mas[i];
    }
    for(int j = 1; j < dd; j++) {
        for(int i = 0; i < n; i++) {
            int r = i + (1 << (j-1));
            r = min(r, n-1);
            mx[i][j] = max(mx[i][j-1], mx[r][j-1]);
        }
    }

}
vector<int> gr[dydis];
int h[dydis];
void dfs(int v) {
    for(auto x : gr[v]) {
        h[x] = h[v] + 1;
        dfs(x);
    }
}
int getMx(int a, int b) {
    int pw = lg2[b - a + 1];
   // cout << a  << "; " << b << " issiskaido i intervala [" << a << "; " << a + (1 << pw) - 1 << "] ir intervala [" <<  b - (1 << pw) + 1 << "; " << b << "]\n";
    int ind = b - (1 << pw) + 1;
    return max(mx[a][pw], mx[ind][pw]);
}
int firstLarger[dydis];

void init(int N, vector<int> H) {
    n = N ;
    mas = H;
    build();
    set<pair<int, int> > setas;
    for(int i = 0; i < n; i++) {
        firstLarger[i] = -1;
        while(setas.size()) {
            if(mas[i] > setas.begin()->first) {
                firstLarger[setas.begin()->second] = i;
                setas.erase(*setas.begin());
            }else break;
        }

        setas.insert({mas[i], i});
    }
    vector<int> roots;
    for(int i = 0; i < n; i++) {
        if(firstLarger[i] == -1) {
            roots.push_back(i);
        }else {
            gr[firstLarger[i]].push_back(i);
        }
    }
    for(auto x : roots) {
        h[x] = 0;
        dfs(x);
    }
}

bool arGalima(int a, int b) { /// ar galima is a i b?
    if(mas[a] >= mas[b]) return false;
    if(a == b-1) return true;
    if(getMx(a+1, b-1) < b) return true;
    return false;
}

int minimum_jumps(int A, int B, int C, int D) {

   // cout << "maximumas tarp " << A << " ir " << C << " yra " <<  getMx(A, C) << endl;
    if(arGalima(A, C) == false) return -1;
    return h[A] - h[C];
}

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