Maximums

#include <algorithm>
#include <iostream>

using namespace std;

// 2 ** 60 - 1 (>= 10 ** 18)
#define MAX_NUMBER 1152921504606846975


struct Node {
    Node* left;
    Node* right;
    unsigned long long max_height;
};


void set_height(Node** tree, unsigned long long a, unsigned long long b,
                unsigned long long i, unsigned long long h) {
    unsigned long long mid = (a + b) / 2;

    if (*tree == NULL) {
        *tree = new Node;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
        (*tree)->max_height = 0;
    }

    if (a == b) {
        (*tree)->max_height = h;
    } else {
        if (i <= mid) {
            set_height(&((*tree)->left), a, mid, i, h);
        } else {
            set_height(&((*tree)->right), mid + 1, b, i, h);
        }

        unsigned long long left_max = 0;
        unsigned long long right_max = 0;

        if ((*tree)->left != NULL) {
            left_max = (*tree)->left->max_height;
        }

        if ((*tree)->right != NULL) {
            right_max = (*tree)->right->max_height;
        }

        (*tree)->max_height = max(left_max, right_max);
    }
}


unsigned long long max_height(
        Node* tree, unsigned long long a, unsigned long long b,
        unsigned long long start, unsigned long long end) {
    if (tree == NULL || (b < start || end < a)) {
        return 0;
    } else if (start <= a && b <= end) {
        return tree->max_height;
    } else {
        unsigned long long mid = (a + b) / 2;
        unsigned long long max_left = max_height(
            tree->left, a, mid, start, end);
        unsigned long long max_right = max_height(
            tree->right, mid + 1, b, start, end);
        return max(max_left, max_right);
    }
}


void free_tree(Node** tree) {
    if (*tree != NULL) {
        free_tree(&((*tree)->left));
        free_tree(&((*tree)->right));

        delete *tree;
        *tree = NULL;
    }
}


int main() {
    int q;
    cin >> q;

    Node* street = NULL;

    for (int i = 0; i < q; i++) {
        unsigned long long t, a, b;
        cin >> t >> a >> b;

        if (t == 0) {
            set_height(&street, 0, MAX_NUMBER, a, b);
        } else {
            cout << max_height(street, 0, MAX_NUMBER, a, b) << endl;
        }
    }

    free_tree(&street);

    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