← Home
For problem statement at 0-999/600-699/610-619/610/problemD.txt this is a correct solution, but verifier at 0-999/600-699/610-619/610/verifierD.go ends with all tests passed can you fix the verifier? ```go
package main

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

type Hor struct {
	y, l, r int64
}

type Ver struct {
	x, low, high int64
}

type Row struct {
	y      int64
	merged [][]int64
}

type Col struct {
	x      int64
	merged [][]int64
}

type Event struct {
	y       int64
	typ     int
	subtyp  int
	is_act  bool
	x       int64
	row_idx int
}

type SegTree struct {
	tree []int64
	n    int
}

func NewSegTree(size int) *SegTree {
	t := &SegTree{}
	t.n = size
	t.tree = make([]int64, 4*size+4)
	return t
}

func (t *SegTree) update(idx int, val int64, node, l, r int) {
	if l == r {
		t.tree[node] += val
		return
	}
	mid := (l + r) / 2
	if idx <= mid {
		t.update(idx, val, node*2, l, mid)
	} else {
		t.update(idx, val, node*2+1, mid+1, r)
	}
	t.tree[node] = t.tree[node*2] + t.tree[node*2+1]
}

func (t *SegTree) query(ql, qr, node, l, r int) int64 {
	if ql > r || qr < l {
		return 0
	}
	if ql <= l && r <= qr {
		return t.tree[node]
	}
	mid := (l + r) / 2
	return t.query(ql, qr, node*2, l, mid) + t.query(ql, qr, node*2+1, mid+1, r)
}

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func mergeAndCalc(intervals [][]int64) (int64, [][]int64) {
	if len(intervals) == 0 {
		return 0, nil
	}
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	cur_l := intervals[0][0]
	cur_r := intervals[0][1]
	var merged [][]int64
	var tot int64
	for k := 1; k < len(intervals); k++ {
		if intervals[k][0] > cur_r {
			tot += cur_r - cur_l + 1
			merged = append(merged, []int64{cur_l, cur_r})
			cur_l = intervals[k][0]
			cur_r = intervals[k][1]
		} else {
			cur_r = max(cur_r, intervals[k][1])
		}
	}
	tot += cur_r - cur_l + 1
	merged = append(merged, []int64{cur_l, cur_r})
	return tot, merged
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)
	var hors []Hor
	var vers []Ver
	for i := 0; i < n; i++ {
		var x1, y1, x2, y2 int64
		fmt.Fscan(reader, &x1, &y1, &x2, &y2)
		if y1 == y2 {
			l := min(x1, x2)
			r := max(x1, x2)
			hors = append(hors, Hor{y: y1, l: l, r: r})
		} else {
			l := min(y1, y2)
			r := max(y1, y2)
			vers = append(vers, Ver{x: x1, low: l, high: r})
		}
	}
	sort.Slice(hors, func(i, j int) bool {
		return hors[i].y < hors[j].y
	})
	var h_total int64
	var rows []Row
	i := 0
	for i < len(hors) {
		curr_y := hors[i].y
		var ints [][]int64
		for i < len(hors) && hors[i].y == curr_y {
			ints = append(ints, []int64{hors[i].l, hors[i].r})
			i++
		}
		tot, merged := mergeAndCalc(ints)
		h_total += tot
		if len(merged) > 0 {
			rows = append(rows, Row{curr_y, merged})
		}
	}
	sort.Slice(vers, func(i, j int) bool {
		return vers[i].x < vers[j].x
	})
	var v_total int64
	var cols []Col
	i = 0
	for i < len(vers) {
		curr_x := vers[i].x
		var ints [][]int64
		for i < len(vers) && vers[i].x == curr_x {
			ints = append(ints, []int64{vers[i].low, vers[i].high})
			i++
		}
		tot, merged := mergeAndCalc(ints)
		v_total += tot
		if len(merged) > 0 {
			cols = append(cols, Col{curr_x, merged})
		}
	}
	var all_x []int64
	for _, c := range cols {
		all_x = append(all_x, c.x)
	}
	sort.Slice(all_x, func(i, j int) bool {
		return all_x[i] < all_x[j]
	})
	m := len(all_x)
	x_to_idx := make(map[int64]int)
	for k := 0; k < m; k++ {
		x_to_idx[all_x[k]] = k + 1
	}
	var events []Event
	for _, c := range cols {
		for _, iv := range c.merged {
			a := iv[0]
			b := iv[1]
			events = append(events, Event{y: a, typ: 0, subtyp: 1, x: c.x})
			events = append(events, Event{y: b + 1, typ: 0, subtyp: 0, x: c.x})
		}
	}
	for ri := range rows {
		events = append(events, Event{y: rows[ri].y, typ: 1, row_idx: ri})
	}
	sort.Slice(events, func(i, j int) bool {
		if events[i].y != events[j].y {
			return events[i].y < events[j].y
		}
		if events[i].typ != events[j].typ {
			return events[i].typ < events[j].typ
		}
		return events[i].subtyp < events[j].subtyp
	})
	var st *SegTree
	if m > 0 {
		st = NewSegTree(m)
	}
	var inter int64
	for _, e := range events {
		if e.typ == 0 {
			idx := x_to_idx[e.x]
			delta := int64(1)
			if e.subtyp == 0 {
				delta = -1
			}
			st.update(idx, delta, 1, 1, m)
		} else {
			var cnt int64
			merged := rows[e.row_idx].merged
			for _, iv := range merged {
				L := iv[0]
				R := iv[1]
				left := sort.Search(len(all_x), func(k int) bool { return all_x[k] >= L })
				right := sort.Search(len(all_x), func(k int) bool { return all_x[k] > R })
				from_idx := left + 1
				to_idx := right
				if from_idx <= to_idx {
					cnt += st.query(from_idx, to_idx, 1, 1, m)
				}
			}
			inter += cnt
		}
	}
	ans := h_total + v_total - inter
	fmt.Println(ans)
}
```