UVa 11226 - Reaching the fix-point

// UVa 11226 - Reaching the fix-point

#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;

#define datatype unsigned long int
#define p2 524288

datatype sopf[500001];
unsigned int lsopf[500001];
unsigned int tree[1048576];

void insert(datatype node, datatype ini, datatype fin, datatype i, unsigned int v) {
	tree[node] = max(tree[node], v);
	if (ini == fin)
		return;
	datatype mid = (ini + fin) >> 1;
	if (mid < i)
		insert(node * 2 + 1, mid + 1, fin, i, v);
	else
		insert(node << 1, ini, mid, i, v);
}

int get(datatype node, datatype ini, datatype fin, datatype a, datatype b) {
	if (a == ini && b == fin)
		return tree[node];
	datatype mid = (ini + fin) >> 1;
	if (a > mid)
		return get(node * 2 + 1, mid + 1, fin, a, b);
	else if (b <= mid)
		return get(node << 1, ini, mid, a, b);
	else {
		unsigned int lf = get(node << 1, ini, mid, a, mid);
		unsigned int rg = get(node * 2 + 1, mid + 1, fin, mid + 1, b);
		return max(lf, rg);
	}
}

int main() {

	for (datatype i = 2; i < 500001; i++) {
		datatype sqrti = sqrt(i);
		bool prime = true;
		for (datatype j = 2; j <= sqrti; j++) {
			lsopf[i] = 0;
			if (i % j == 0) {
				sopf[i] = sopf[i / j] + j;
				lsopf[i] = lsopf[sopf[i]] + 1;
				prime = false;
				break;
			}
		}
		if (prime) {
			sopf[i] = i;
			lsopf[i] = 1;
		}
		insert(1, 1, p2, i, lsopf[i]);
	}

	int tt;
	cin >> tt;
	for (int t = 1; t <= tt; t++) {
		datatype n, m;
		cin >> n >> m;
		if (n > m) {
			datatype tmp = n;
			n = m;
			m = tmp;
		}
		unsigned int mx = get(1, 1, p2, n, m);
		printf("Case #%d:\n%u\n", t, mx);
	}
	return 0;
}