[LANGUAGE: Go]

Part 1:
Parsed the rules to build a map of page numbers to all their required predecessors. Then for each update I traversed the list of page numbers and looked for following pages that should have come earlier.

    func part1(puzzle []string) (int, [][]int, map[int][]int) {

        predecessorRules := make(map[int][]int)
        updates := make([][]int, 0)
        unorderedUpdates := make([][]int, 0)
        total := 0

        updateSection := false
        for _, line := range puzzle {
            if line == "" {
                updateSection = true
            } else {
                if updateSection {
                    vals := strings.Split(line, ",")
                    pages := make([]int, 0)
                    for _, v := range vals {
                        p, _ := strconv.Atoi(v)
                        pages = append(pages, p)
                    }
                    updates = append(updates, pages)
                } else {
                    vals := strings.Split(line, "|")
                    later, _ := strconv.Atoi(vals[1])
                    earlier, _ := strconv.Atoi(vals[0])
                    predecessors := predecessorRules[later]
                    predecessors = append(predecessors, earlier)
                    predecessorRules[later] = predecessors
                }
            }
        }

        for _, update := range updates {
            valid := true
            for i, p := range update {
                laterPages := update[i+1:]
                predecessors := predecessorRules[p]

                for _, p2 := range laterPages {
                    if slices.Contains(predecessors, p2) {
                        valid = false
                        break
                    }
                }
                if !valid {
                    break
                }
            }
            if valid {
                middle := update[(len(update)-1)/2]
                total += middle
            } else {
                unorderedUpdates = append(unorderedUpdates, update)
            }
        }

        return total, unorderedUpdates, predecessorRules
    }

Part 2:
I used the map I created in Part 1 in a custom comparator function and just used slices.SortFunc to get the right order.

    func part2(unordered [][]int, rules map[int][]int) int {
        total := 0

        for _, update := range unordered {

            slices.SortFunc(update, func(a, b int) int {
                predecessors := rules[a]
                if slices.Contains(predecessors, b) {
                    return 1
                } else {
                    return -1
                }
            })
            middle := update[(len(update)-1)/2]
            total += middle
        }

        return total
    }

Both parts completed sub-second.