← Home
For problem statement at 1000-1999/1300-1399/1370-1379/1371/problemF.txt this is a correct solution, but verifier at 1000-1999/1300-1399/1370-1379/1371/verifierF.go ends with All tests passed can you fix the verifier? package main

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

type Node struct {
	ansDec, ansInc   int32
	pref0, pref1     int32
	prefDec, prefInc int32
	suff0, suff1     int32
	suffDec, suffInc int32
	len              int32
	lazy             bool
}

var tree []Node

func max32(a, b int32) int32 {
	if a > b {
		return a
	}
	return b
}

func merge(L, R Node) Node {
	var res Node
	res.len = L.len + R.len

	if L.pref0 == L.len {
		res.pref0 = L.len + R.pref0
	} else {
		res.pref0 = L.pref0
	}
	if L.pref1 == L.len {
		res.pref1 = L.len + R.pref1
	} else {
		res.pref1 = L.pref1
	}

	if R.suff0 == R.len {
		res.suff0 = R.len + L.suff0
	} else {
		res.suff0 = R.suff0
	}
	if R.suff1 == R.len {
		res.suff1 = R.len + L.suff1
	} else {
		res.suff1 = R.suff1
	}

	if L.prefDec == L.len {
		if L.pref1 == L.len {
			res.prefDec = L.len + R.prefDec
		} else {
			res.prefDec = L.len + R.pref0
		}
	} else {
		res.prefDec = L.prefDec
	}

	if L.prefInc == L.len {
		if L.pref0 == L.len {
			res.prefInc = L.len + R.prefInc
		} else {
			res.prefInc = L.len + R.pref1
		}
	} else {
		res.prefInc = L.prefInc
	}

	if R.suffDec == R.len {
		if R.suff0 == R.len {
			res.suffDec = R.len + L.suffDec
		} else {
			res.suffDec = R.len + L.suff1
		}
	} else {
		res.suffDec = R.suffDec
	}

	if R.suffInc == R.len {
		if R.suff1 == R.len {
			res.suffInc = R.len + L.suffInc
		} else {
			res.suffInc = R.len + L.suff0
		}
	} else {
		res.suffInc = R.suffInc
	}

	res.ansDec = max32(L.ansDec, R.ansDec)
	res.ansDec = max32(res.ansDec, L.suff1+R.prefDec)
	res.ansDec = max32(res.ansDec, L.suffDec+R.pref0)

	res.ansInc = max32(L.ansInc, R.ansInc)
	res.ansInc = max32(res.ansInc, L.suff0+R.prefInc)
	res.ansInc = max32(res.ansInc, L.suffInc+R.pref1)

	res.lazy = false
	return res
}

func (n *Node) flip() {
	n.pref0, n.pref1 = n.pref1, n.pref0
	n.suff0, n.suff1 = n.suff1, n.suff0
	n.prefDec, n.prefInc = n.prefInc, n.prefDec
	n.suffDec, n.suffInc = n.suffInc, n.suffDec
	n.ansDec, n.ansInc = n.ansInc, n.ansDec
	n.lazy = !n.lazy
}

func push(node int) {
	if tree[node].lazy {
		tree[2*node].flip()
		tree[2*node+1].flip()
		tree[node].lazy = false
	}
}

func build(node, l, r int, s string) {
	if l == r {
		tree[node].len = 1
		if s[l-1] == '>' {
			tree[node].pref1 = 1
			tree[node].suff1 = 1
			tree[node].ansDec = 1
			tree[node].ansInc = 1
			tree[node].prefDec = 1
			tree[node].prefInc = 1
			tree[node].suffDec = 1
			tree[node].suffInc = 1
		} else {
			tree[node].pref0 = 1
			tree[node].suff0 = 1
			tree[node].ansDec = 1
			tree[node].ansInc = 1
			tree[node].prefDec = 1
			tree[node].prefInc = 1
			tree[node].suffDec = 1
			tree[node].suffInc = 1
		}
		return
	}
	mid := (l + r) / 2
	build(2*node, l, mid, s)
	build(2*node+1, mid+1, r, s)
	tree[node] = merge(tree[2*node], tree[2*node+1])
}

func update(node, l, r, ql, qr int) {
	if ql <= l && r <= qr {
		tree[node].flip()
		return
	}
	push(node)
	mid := (l + r) / 2
	if ql <= mid {
		update(2*node, l, mid, ql, qr)
	}
	if qr > mid {
		update(2*node+1, mid+1, r, ql, qr)
	}
	tree[node] = merge(tree[2*node], tree[2*node+1])
}

func query(node, l, r, ql, qr int) Node {
	if ql <= l && r <= qr {
		return tree[node]
	}
	push(node)
	mid := (l + r) / 2
	if qr <= mid {
		return query(2*node, l, mid, ql, qr)
	}
	if ql > mid {
		return query(2*node+1, mid+1, r, ql, qr)
	}
	return merge(query(2*node, l, mid, ql, qr), query(2*node+1, mid+1, r, ql, qr))
}

func readInt(in *bufio.Reader) int {
	n := 0
	c, err := in.ReadByte()
	for err == nil && c <= ' ' {
		c, err = in.ReadByte()
	}
	if err != nil {
		return 0
	}
	for err == nil && c > ' ' {
		n = n*10 + int(c-'0')
		c, err = in.ReadByte()
	}
	return n
}

func readString(in *bufio.Reader) string {
	var b []byte
	c, err := in.ReadByte()
	for err == nil && c <= ' ' {
		c, err = in.ReadByte()
	}
	if err != nil {
		return ""
	}
	for err == nil && c > ' ' {
		b = append(b, c)
		c, err = in.ReadByte()
	}
	return string(b)
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	n := readInt(in)
	q := readInt(in)
	s := readString(in)

	tree = make([]Node, 4*n+1)
	build(1, 1, n, s)

	for i := 0; i < q; i++ {
		l := readInt(in)
		r := readInt(in)
		update(1, 1, n, l, r)
		res := query(1, 1, n, l, r)
		fmt.Fprintln(out, res.ansDec)
	}
}