Does Contamination's upkeep cost have to be paid before or after you untap your lands?

The turn structure places the Untap Step first, then the Upkeep Step second (CR 500.1, 501.1, 502.1). Contamination's triggered ability — sacrifice a creature or sacrifice Contamination — triggers at the beginning of your upkeep, meaning it goes on the stack during the Upkeep Step, well after your permanents have already untapped.

Specifically, CR 502.1 states that the Upkeep Step begins after the Untap Step has completed. Any "at the beginning of your upkeep" triggered abilities trigger at the start of that step, are put on the stack, and then players receive priority to respond (CR 502.2). So by the time you're paying Contamination's upkeep cost, your lands and other permanents are already untapped.

This matters practically: you can sacrifice a creature token you just untapped, or use any resource that became available during the Untap Step, to pay the cost. Your mana-producing lands are also already untapped if you need them for anything in response.

Concrete example: You control Contamination and a Llanowar Elves. At the start of your turn, your Untap Step happens — both Contamination and Llanowar Elves untap. Then, during Upkeep, Contamination's trigger goes on the stack. You sacrifice the now-untapped Llanowar Elves to keep Contamination in play. This is perfectly legal because untapping happened first.

Key rules references: CR 500.1 (turn structure), CR 501.1 (Untap Step), CR 502.1–502.2 (Upkeep Step), and CR 603.3 (triggered abilities triggering at start of a step).