For problem statement at 1000-1999/1300-1399/1360-1369/1368/problemG.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1360-1369/1368/verifierG.go ends with candidate runtime error on test 1: exit status 2
input:
4 1
0
0
0
0
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
"sort"
)
type Event struct {
x int
y1 int
y2 int
val int
}
var cnt []int
var length []int
func update(node, l, r, ql, qr, val int) {
if ql <= l && r <= qr {
cnt[node] += val
} else {
mid := (l + r) / 2
if ql <= mid {
update(2*node, l, mid, ql, qr, val)
}
if qr > mid {
update(2*node+1, mid+1, r, ql, qr, val)
}
}
if cnt[node] > 0 {
length[node] = r - l + 1
} else if l == r {
length[node] = 0
} else {
length[node] = length[2*node] + length[2*node+1]
}
}
func processGraph(target []int) ([]int, []int, []int, int) {
N := len(target) - 1
rep := make([]int, N+1)
for i := 0; i <= N; i++ {
rep[i] = i
}
vis := make([]int, N+1)
for i := 0; i <= N; i++ {
if vis[i] == 0 {
curr := i
for vis[curr] == 0 {
vis[curr] = 1
curr = target[curr]
}
if vis[curr] == 1 {
cs := curr
rep[curr] = cs
curr = target[curr]
for curr != cs {
rep[curr] = cs
curr = target[curr]
}
}
curr = i
for vis[curr] == 1 {
vis[curr] = 2
curr = target[curr]
}
}
}
adj := make([][]int, N+1)
for i := 0; i <= N; i++ {
u := i
v := target[i]
if rep[u] != rep[v] {
adj[rep[v]] = append(adj[rep[v]], rep[u])
}
}
in := make([]int, N+1)
out := make([]int, N+1)
timer := 0
var dfs func(int)
dfs = func(u int) {
timer++
in[u] = timer
for _, v := range adj[u] {
dfs(v)
}
out[u] = timer
}
for i := 0; i <= N; i++ {
if rep[i] == i {
dfs(i)
}
}
return in, out, rep, timer
}
func main() {
reader := bufio.NewReader(os.Stdin)
var n, m int
fmt.Fscanf(reader, "%d %d\n", &n, &m)
board := make([]string, n)
for i := 0; i < n; i++ {
fmt.Fscanf(reader, "%s\n", &board[i])
}
NCells := n * m / 2
idB := make([][]int, n)
idW := make([][]int, n)
for i := 0; i < n; i++ {
idB[i] = make([]int, m)
idW[i] = make([]int, m)
for j := 0; j < m; j++ {
idB[i][j] = -1
idW[i][j] = -1
}
}
cntB, cntW := 0, 0
for r := 0; r < n; r++ {
for c := 0; c < m; c++ {
if (r+c)%2 == 0 {
idB[r][c] = cntB
cntB++
} else {
idW[r][c] = cntW
cntW++
}
}
}
targetB := make([]int, NCells+1)
targetW := make([]int, NCells+1)
for i := 0; i <= NCells; i++ {
targetB[i] = NCells
targetW[i] = NCells
}
type Domino struct{ b, w int }
doms := make([]Domino, 0, NCells)
for r := 0; r < n; r++ {
for c := 0; c < m; c++ {
tr, tc := r, c
ch := board[r][c]
if ch == 'U' {
tr += 2
} else if ch == 'D' {
tr -= 2
} else if ch == 'L' {
tc += 2
} else if ch == 'R' {
tc -= 2
}
isB := (r+c)%2 == 0
if tr >= 0 && tr < n && tc >= 0 && tc < m {
if isB {
targetB[idB[r][c]] = idB[tr][tc]
} else {
targetW[idW[r][c]] = idW[tr][tc]
}
}
if ch == 'U' {
b, w := idB[r][c], idW[r+1][c]
if !isB {
b, w = idB[r+1][c], idW[r][c]
}
doms = append(doms, Domino{b, w})
} else if ch == 'L' {
b, w := idB[r][c], idW[r][c+1]
if !isB {
b, w = idB[r][c+1], idW[r][c]
}
doms = append(doms, Domino{b, w})
}
}
}
inB, outB, repB, _ := processGraph(targetB)
inW, outW, repW, timerW := processGraph(targetW)
events := make([]Event, 0, 2*len(doms))
for _, d := range doms {
x1 := inB[repB[d.b]]
x2 := outB[repB[d.b]]
y1 := inW[repW[d.w]]
y2 := outW[repW[d.w]]
events = append(events, Event{x1, y1, y2, 1})
events = append(events, Event{x2 + 1, y1, y2, -1})
}
sort.Slice(events, func(i, j int) bool {
return events[i].x < events[j].x
})
cnt = make([]int, 4*(timerW+5))
length = make([]int, 4*(timerW+5))
ans := int64(0)
prevX := events[0].x
ptr := 0
for ptr < len(events) {
currX := events[ptr].x
ans += int64(length[1]) * int64(currX-prevX)
prevX = currX
for ptr < len(events) && events[ptr].x == currX {
update(1, 1, timerW, events[ptr].y1, events[ptr].y2, events[ptr].val)
ptr++
}
}
fmt.Println(ans)
}