← Home
For problem statement at 1000-1999/1900-1999/1930-1939/1936/problemE.txt this is a correct solution, but verifier at 1000-1999/1900-1999/1930-1939/1936/verifierE.go ends with All tests passed can you fix the verifier? package main

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

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 1024*1024)
	writer := bufio.NewWriterSize(os.Stdout, 1024*1024)
	defer writer.Flush()

	var t int
	fmt.Fscan(reader, &t)

	for tc := 0; tc < t; tc++ {
		var n int
		fmt.Fscan(reader, &n)

		p := make([]int, n)
		for i := 0; i < n; i++ {
			fmt.Fscan(reader, &p[i])
		}

		l := make([]int, n+1)
		r := make([]int, n+1)
		for i := 0; i <= n; i++ {
			l[i] = n + 1
			r[i] = -1
		}

		curMax := 0
		for i := 0; i < n-1; i++ {
			if p[i] > curMax {
				curMax = p[i]
			}
			if i+1 < l[curMax] {
				l[curMax] = i + 1
			}
			if i+1 > r[curMax] {
				r[curMax] = i + 1
			}
		}

		dp := make([]uint32, n+1)
		dp[n] = 1

		for x := n; x >= 1; x-- {
			lx := l[x]
			rx := r[x]

			if lx > n {
				var s uint32 = 0
				for k := x; k >= 0; k-- {
					v := dp[k]
					if v == 0 && s == 0 {
						continue
					}
					dp[k] = uint32((uint64(v)*uint64(x-k) + uint64(s)) % 998244353)
					s += v
					if s >= 998244353 {
						s -= 998244353
					}
				}
			} else {
				var sHigh uint32 = 0
				for k := x; k >= rx; k-- {
					v := dp[k]
					if v == 0 && sHigh == 0 {
						continue
					}
					dp[k] = uint32((uint64(v)*uint64(x-k) + uint64(sHigh)) % 998244353)
					sHigh += v
					if sHigh >= 998244353 {
						sHigh -= 998244353
					}
				}
				var sLow uint32 = 0
				for k := rx - 1; k >= lx-1; k-- {
					v := dp[k]
					if v > 0 {
						dp[k] = uint32((uint64(v) * uint64(x-k)) % 998244353)
					}
					if k <= lx-1 {
						sLow += v
						if sLow >= 998244353 {
							sLow -= 998244353
						}
					}
				}
				for k := lx - 2; k >= 0; k-- {
					v := dp[k]
					if v == 0 && sLow == 0 {
						continue
					}
					dp[k] = uint32((uint64(v)*uint64(x-k) + uint64(sLow)) % 998244353)
					sLow += v
					if sLow >= 998244353 {
						sLow -= 998244353
					}
				}
			}
		}
		fmt.Fprintln(writer, dp[0])
	}
}