Maximums

#include <iostream>

using namespace std;
typedef long long ll;

const ll INF = 1000000000000000005;
const ll N = 1LL<<60; // max element index

struct node {
    ll s;
    node *l, *r;
    node (ll cs) : s(cs) {
        l = nullptr;
        r = nullptr;
    }
};

node *st = new node(0LL); // segtree root node

void update(ll k, ll val, ll x, ll y, node *nd = st) {
    if (x == y) {
        nd->s = val;
    }
    else {
        ll mid = (x+y)/2;
        if (x <= k && k <= mid) {
            if (nd->l == nullptr) nd->l = new node(0LL);
            update(k, val, x, mid, nd->l);
        }
        else if (mid < k && k <= y) {
            if (nd->r == nullptr) nd->r = new node(0LL);
            update(k, val, mid+1, y, nd->r);
        }
        ll ns = -INF;
        if (nd->l != nullptr) ns = max(ns, (nd->l)->s);
        if (nd->r != nullptr) ns = max(ns, (nd->r)->s);
        nd->s = ns;
    }
}

ll query(ll ql, ll qr, ll x, ll y, node *nd = st) {
    if (ql <= x && y <= qr) return nd->s;
    if (y < ql || x > qr) return -INF;
    ll mid = (x+y)/2;
    ll res = -INF;
    if (nd->l != nullptr) res = max(res, query(ql, qr, x, mid, nd->l));
    if (nd->r != nullptr) res = max(res, query(ql, qr, mid+1, y, nd->r));
    return res;
}

int qcnt;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> qcnt;
	for (int cq = 0; cq < qcnt; ++cq) {
		int tp;
		cin >> tp;
		if (tp == 0) {
			ll k, x;
			cin >> k >> x;
			update(k, x, 0, N-1, st);
		}
		else {
			ll a, b;
			cin >> a >> b;
			if (a > b) swap(a, b);
			ll cres = query(a, b, 0, N-1, st);
			cres = max(0LL, cres);
			cout << cres << "\n";
		}
	}
	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