I've seen so many blog posts about cheating, but seeing the latest educational round, I'd say things are getting out of hand, mainly because for some odd reason cheating in codeforces doesn't have a very harsh punishment(discussed in this awesome blog post). I'd say participating in div2 contests is not as fun as before since you really don't have a chance against cheaters, best represented by my good friend theSkeleton who's got a max rating of 1899 because of these people.

p.s. Position 11 just cracks me up, my guy full-marked the contest in 6 minutes

I recently solved 1439C - Greedy Shopping using a segment tree which stores the sum(sum array), min(mn array) and max(mx array) 306106940, I used the following function to process the queries:

pii GET(int id, int l, int r, int x) {
	if(x < mn[id]) return mp(0, 0);
	if(x >= sum[id]) return mp(r-l, sum[id]);
	PUSH(id, l, r);
	pii p1 = GET(lc, l, mid, x); pii p2 = GET(rc, mid, r, x-p1.Y);
	return mp(p1.X+p2.X, p1.Y+p2.Y);
}

At first glance, I thought the time complexity should be O(log(n)²), since the purchased items form some blocks of the array. Since each block at least halves the remaining money, we have O(log(n)) blocks in the array. More so, each block of size k corresponds to O(log(k)) nodes in the segment tree, meaning we must traverse O(log(n)²) blocks in the segment tree, however increasing the number of blocks decreases the sum of the logarithms of the block sizes, so we might traverse less nodes in the segment tree. Despite trying, I could not figure out a definite time complexity for this function and I would greatly appreciate any help to form a vague proof of this function's actual time complexity.