Well I tried it in Go and the solution is pretty slow but...

package main

import (
    "fmt"
    "sort"
)

type Sheet struct {
    x1     int
    x2     int
    y1     int
    y2     int
    colour int
}

func main() {
    x, y := getBaseSheet()
    sheets := make([]Sheet, 100)

    for sheet, err := getSheet(); err == nil; sheet, err = getSheet() {
        sheets = append(sheets, sheet)
    }

    var zeroes int
    sMax := len(sheets) - 1
    colours := map[int]int{}
    for j := 0; j < y; j++ {
        zeroes = x
        for i := 0; i < x; i++ {
            for s := sMax; s >= 0; s-- {
                if sheets[s].contains(i, j) {
                    count := sheets[s].x2 - i + 1
                    colours[sheets[s].colour] += count
                    zeroes -= count
                    i = sheets[s].x2
                    break
                }
            }
        }
        colours[0] += zeroes
    }

    var keys []int
    for i := range colours {
        keys = append(keys, i)
    }
    sort.Ints(keys)

    for i := 0; i < len(keys); i++ {
        fmt.Printf("%d %d\n", i, colours[i])
    }
}

func getBaseSheet() (int, int) {
    var x, y int
    fmt.Scanln(&x, &y)
    return x, y
}

func getSheet() (Sheet, error) {
    var colour, x, y, width, height int
    _, err := fmt.Scanln(&colour, &x, &y, &width, &height)
    if err != nil {
        return Sheet{}, err
    }

    return Sheet{x, x + width - 1, y, y + height - 1, colour}, nil
}

func (sheet Sheet) contains(x, y int) bool {
    return x >= sheet.x1 && x <= sheet.x2 && y >= sheet.y1 && y <= sheet.y2
}

It works, albeit slowly. Any feedback is appreciated.

$ echo "20 10
1 5 5 10 3
2 0 0 7 7
" | ./paper
0 125
1 26
2 49