← Home
For problem statement at 1000-1999/1500-1599/1550-1559/1555/problemE.txt this is a correct solution, but verifier at 1000-1999/1500-1599/1550-1559/1555/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var reader = bufio.NewReaderSize(os.Stdin, 65536)

func nextInt() int {
	res := 0
	for {
		b, err := reader.ReadByte()
		if err != nil {
			return res
		}
		if b >= '0' && b <= '9' {
			res = int(b - '0')
			for {
				b, err = reader.ReadByte()
				if err != nil || b < '0' || b > '9' {
					return res
				}
				res = res*10 + int(b-'0')
			}
		}
	}
}

type Segment struct {
	l, r, w int
}

var min_val []int
var lazy []int

func update(node, start, end, l, r, val int) {
	if start > r || end < l {
		return
	}
	if start >= l && end <= r {
		min_val[node] += val
		lazy[node] += val
		return
	}
	mid := (start + end) / 2
	update(2*node, start, mid, l, r, val)
	update(2*node+1, mid+1, end, l, r, val)
	m1 := min_val[2*node]
	m2 := min_val[2*node+1]
	if m2 < m1 {
		m1 = m2
	}
	min_val[node] = m1 + lazy[node]
}

func main() {
	n := nextInt()
	if n == 0 {
		return
	}
	m := nextInt()

	segments := make([]Segment, n)
	for i := 0; i < n; i++ {
		segments[i].l = nextInt()
		segments[i].r = nextInt()
		segments[i].w = nextInt()
	}

	sort.Slice(segments, func(i, j int) bool {
		return segments[i].w < segments[j].w
	})

	min_val = make([]int, 4*m+4)
	lazy = make([]int, 4*m+4)

	ans := int(2e9)
	L := 0
	for R := 0; R < n; R++ {
		update(1, 1, m-1, segments[R].l, segments[R].r-1, 1)
		for min_val[1] > 0 {
			diff := segments[R].w - segments[L].w
			if diff < ans {
				ans = diff
			}
			update(1, 1, m-1, segments[L].l, segments[L].r-1, -1)
			L++
		}
	}

	fmt.Println(ans)
}