Frog and flies

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int parent(int node) {
    return node / 2;
}

int left(int node) {
    return 2 * node;
}

int right(int node) {
    return 2 * node + 1;
}

ll getMax(int a, int b, vector<ll>& arr) {
    int n = arr.size() / 2;
    a += n; b += n;
    ll maxVal = 0;
    while (a <= b) {
        if (a%2 == 1) {
            maxVal = max(maxVal, arr[a]);
            a++;
        }
        if (b%2 == 0) {
            maxVal = max(maxVal, arr[b]);
            b--;
        }
        a = parent(a);
        b = parent(b);
    }
    return maxVal;
}

void setVal(int ind, int val, vector<ll>& arr) {
    int n = arr.size() / 2;
    ind += n;
    arr[ind] = val;
    for (ind /= 2; ind >= 1; ind /= 2) {
        arr[ind] = max(arr[left(ind)], arr[right(ind)]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n;
    cin >> n;

    int elems = 1 << (int)ceil(log2(n));
    vector<ll> tree(2*elems, 0);

    // min, max
    vector<pair<int, int>> adj(elems);

    ll a, b, c;
    for (ll i=0; i<n; i++) {
        cin >> a >> b >> c;
        b--; c--;
        tree[i + elems] = a;
        adj[i] = pair<int, int>(max(i+1, b), c);
    }

    for (int i=elems-1; i>0; i--) {
        tree[i] = max(tree[left(i)], tree[right(i)]);
    }

    ll best = 0;
    for (int i=n-1; i>=0; i--) {
        int left = adj[i].first;
        int right = adj[i].second;
        if (left > right) {
            continue;
        }
        ll tmp_best = tree[i + elems] + getMax(adj[i].first, adj[i].second, tree);
        setVal(i, max(tmp_best, tree[i + elems]), tree);
        best = max(best, tmp_best);
    }

    cout << best << endl;

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED