Submission #613748

#	Time	Username	Problem	Language	Result	Execution time	Memory
613748		AugustinasJucas	Rainforest Jumps (APIO21_jumps)	C++14	37 / 100	4030 ms	41000 KiB

jumps

#include "jumps.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> mas;
bool line = true;
const int dydis = 2e5 + 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];
int lastLarger[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++) {
        if(mas[i] != i+1) line = false;
        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});
    }

    setas.clear();
    for(int i = n-1; i > -1; i--) {
        lastLarger[i] = -1;
        while(setas.size()) {
            if(mas[i] > setas.begin()->first) {
                lastLarger[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);
    }*/
    for(int i = 0; i < n; i++) {
      //  cout << "nuo " << i << " is kaires - " << lastLarger[i] << ", o is desines " << firstLarger[i] << endl;
        if(lastLarger[i] != -1) gr[i].push_back(lastLarger[i]);
        if(firstLarger[i] != -1) gr[i].push_back(firstLarger[i]);
    }
}

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;
}
const int inf = 1e9;
int dist[dydis];
void bfs(int A, int B) {

    queue<int> q;
    for(int i = 0; i < n; i++) {
        dist[i] = inf;
    }
    for(int i = A; i <= B; i++) {
        dist[i] = 0;
        q.push(i);
    }
    while(q.size()) {
        int v = q.front();
        q.pop();
        for(auto x : gr[v]) {
         //   cout << "is " << v << " galiu eiti i " << x << endl;

            if(dist[x] > dist[v] + 1) {
          //      cout << "nustatau dist[" << x << "] = " << dist[v] + 1 << endl;
                dist[x] = dist[v] + 1;
                q.push(x);
            }
        }
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    if(line) {
        return C - B;
    }
    bfs(A, B);
    int ret = inf;
    for(int i = C; i <= D; i++) {
    //    cout << "dist[" << i << "
        ret = min(ret, dist[i]);
    }
    if(ret == inf) return -1;
    return ret;
   // 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: 4 / 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