For problem statement at 0-999/500-599/520-529/527/problemC.txt this is a correct solution, but verifier at 0-999/500-599/520-529/527/verifierC.go ends with all 100 tests passed can you fix the verifier? package main
import (
"bufio"
"container/heap"
"fmt"
"math/rand"
"os"
"time"
)
type Node struct {
key int
pri int64
left *Node
right *Node
}
func newNode(k int) *Node {
return &Node{key: k, pri: rand.Int63()}
}
func rotateRight(y *Node) *Node {
x := y.left
t2 := x.right
x.right = y
y.left = t2
return x
}
func rotateLeft(x *Node) *Node {
y := x.right
t2 := y.left
y.left = x
x.right = t2
return y
}
func insert(root *Node, k int) *Node {
if root == nil {
return newNode(k)
}
if k < root.key {
root.left = insert(root.left, k)
if root.left.pri > root.pri {
root = rotateRight(root)
}
} else {
root.right = insert(root.right, k)
if root.right.pri > root.pri {
root = rotateLeft(root)
}
}
return root
}
func findFloor(root *Node, x int) int {
res := -1
cur := root
for cur != nil {
if cur.key <= x {
res = cur.key
cur = cur.right
} else {
cur = cur.left
}
}
return res
}
func findCeil(root *Node, x int) int {
res := -1
cur := root
for cur != nil {
if cur.key >= x {
res = cur.key
cur = cur.left
} else {
cur = cur.right
}
}
return res
}
type MaxHeap []int
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func getMax(hp *MaxHeap, cnt map[int]int) int {
for len(*hp) > 0 {
top := (*hp)[0]
if cnt[top] > 0 {
return top
}
heap.Pop(hp)
}
return 0
}
func main() {
rand.Seed(time.Now().UnixNano())
reader := bufio.NewReader(os.Stdin)
var w, h, n int
fmt.Fscanf(reader, "%d %d %d\n", &w, &h, &n)
var vx *Node
vx = insert(vx, 0)
vx = insert(vx, w)
vcount := make(map[int]int)
vcount[w] = 1
var vheap MaxHeap
heap.Init(&vheap)
heap.Push(&vheap, w)
var hy *Node
hy = insert(hy, 0)
hy = insert(hy, h)
hcount := make(map[int]int)
hcount[h] = 1
var hheap MaxHeap
heap.Init(&hheap)
heap.Push(&hheap, h)
for i := 0; i < n; i++ {
line, _ := reader.ReadString('\n')
var typ rune
var pos int
fmt.Sscanf(line, "%c %d", &typ, &pos)
if typ == 'V' {
left := findFloor(vx, pos)
right := findCeil(vx, pos)
old := right - left
vcount[old]--
new1 := pos - left
new2 := right - pos
vcount[new1]++
if vcount[new1] == 1 {
heap.Push(&vheap, new1)
}
vcount[new2]++
if vcount[new2] == 1 {
heap.Push(&vheap, new2)
}
vx = insert(vx, pos)
} else {
left := findFloor(hy, pos)
right := findCeil(hy, pos)
old := right - left
hcount[old]--
new1 := pos - left
new2 := right - pos
hcount[new1]++
if hcount[new1] == 1 {
heap.Push(&hheap, new1)
}
hcount[new2]++
if hcount[new2] == 1 {
heap.Push(&hheap, new2)
}
hy = insert(hy, pos)
}
maxv := getMax(&vheap, vcount)
maxh := getMax(&hheap, hcount)
fmt.Println(int64(maxv) * int64(maxh))
}
}