For problem statement at 0-999/700-799/790-799/796/problemF.txt this is a correct solution, but verifier at 0-999/700-799/790-799/796/verifierF.go ends with Wrong answer on test 3
Input:
5 8
2 3 61
2 3 18
2 1 51
2 5 85
2 1 66
2 5 73
2 2 31
2 4 0
Expected:YES
1000000000 1000000000 1000000000 1000000000 1000000000
Got:YES
536870911 1000000000 1000000000 1000000000 1000000000
exit status 1 can you fix the verifier? package main
import (
"bufio"
"fmt"
"os"
)
type Op struct {
t, l, r, x, k, d int
}
var (
lazy []int
limit []int
maxUpd []int
maxUnupd []int
maxUnupdIdx []int
)
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func buildST1(node, l, r int) {
lazy[node] = 1000000000
if l == r {
return
}
mid := (l + r) / 2
buildST1(2*node, l, mid)
buildST1(2*node+1, mid+1, r)
}
func updateST1(node, l, r, ql, qr, val int) {
if ql <= l && r <= qr {
if val < lazy[node] {
lazy[node] = val
}
return
}
mid := (l + r) / 2
if ql <= mid {
updateST1(2*node, l, mid, ql, qr, val)
}
if qr > mid {
updateST1(2*node+1, mid+1, r, ql, qr, val)
}
}
func queryST1(node, l, r, idx int) int {
res := lazy[node]
if l == r {
return res
}
mid := (l + r) / 2
if idx <= mid {
v := queryST1(2*node, l, mid, idx)
if v < res {
res = v
}
} else {
v := queryST1(2*node+1, mid+1, r, idx)
if v < res {
res = v
}
}
return res
}
func buildST2(node, l, r int) {
maxUpd[node] = -1
if l == r {
maxUnupd[node] = limit[l]
maxUnupdIdx[node] = l
return
}
mid := (l + r) / 2
buildST2(2*node, l, mid)
buildST2(2*node+1, mid+1, r)
pushUpST2(node)
}
func pushUpST2(node int) {
maxUpd[node] = max(maxUpd[2*node], maxUpd[2*node+1])
if maxUnupd[2*node] >= maxUnupd[2*node+1] {
maxUnupd[node] = maxUnupd[2*node]
maxUnupdIdx[node] = maxUnupdIdx[2*node]
} else {
maxUnupd[node] = maxUnupd[2*node+1]
maxUnupdIdx[node] = maxUnupdIdx[2*node+1]
}
}
func updateUpd(node, l, r, idx, val int) {
if l == r {
maxUpd[node] = val
return
}
mid := (l + r) / 2
if idx <= mid {
updateUpd(2*node, l, mid, idx, val)
} else {
updateUpd(2*node+1, mid+1, r, idx, val)
}
pushUpST2(node)
}
func updateUnupd(node, l, r, idx, val int) {
if l == r {
maxUnupd[node] = val
return
}
mid := (l + r) / 2
if idx <= mid {
updateUnupd(2*node, l, mid, idx, val)
} else {
updateUnupd(2*node+1, mid+1, r, idx, val)
}
pushUpST2(node)
}
func queryMaxUpd(node, l, r, ql, qr int) int {
if ql <= l && r <= qr {
return maxUpd[node]
}
mid := (l + r) / 2
res := -1
if ql <= mid {
res = max(res, queryMaxUpd(2*node, l, mid, ql, qr))
}
if qr > mid {
res = max(res, queryMaxUpd(2*node+1, mid+1, r, ql, qr))
}
return res
}
func queryMaxUnupd(node, l, r, ql, qr int) (int, int) {
if ql <= l && r <= qr {
return maxUnupd[node], maxUnupdIdx[node]
}
mid := (l + r) / 2
resVal := -1
resIdx := -1
if ql <= mid {
v, idx := queryMaxUnupd(2*node, l, mid, ql, qr)
if v > resVal {
resVal = v
resIdx = idx
}
}
if qr > mid {
v, idx := queryMaxUnupd(2*node+1, mid+1, r, ql, qr)
if v > resVal {
resVal = v
resIdx = idx
}
}
return resVal, resIdx
}
func main() {
reader := bufio.NewReader(os.Stdin)
var n, m int
fmt.Fscan(reader, &n, &m)
ops := make([]Op, m)
firstUpdate := make([]int, n+1)
for i := 0; i < m; i++ {
var typ int
fmt.Fscan(reader, &typ)
if typ == 1 {
var l, r, x int
fmt.Fscan(reader, &l, &r, &x)
ops[i] = Op{t: 1, l: l, r: r, x: x}
} else {
var k, d int
fmt.Fscan(reader, &k, &d)
ops[i] = Op{t: 2, k: k, d: d}
if firstUpdate[k] == 0 {
firstUpdate[k] = i + 1
}
}
}
lazy = make([]int, 4*n+1)
buildST1(1, 1, n)
limit = make([]int, n+1)
for i := 0; i < m; i++ {
if ops[i].t == 1 {
updateST1(1, 1, n, ops[i].l, ops[i].r, ops[i].x)
} else {
if firstUpdate[ops[i].k] == i+1 {
limit[ops[i].k] = queryST1(1, 1, n, ops[i].k)
}
}
}
for k := 1; k <= n; k++ {
if firstUpdate[k] == 0 {
limit[k] = queryST1(1, 1, n, k)
}
}
maxUpd = make([]int, 4*n+1)
maxUnupd = make([]int, 4*n+1)
maxUnupdIdx = make([]int, 4*n+1)
buildST2(1, 1, n)
required := make([]bool, n+1)
a := make([]int, n+1)
for i := 0; i < m; i++ {
if ops[i].t == 1 {
mUpd := queryMaxUpd(1, 1, n, ops[i].l, ops[i].r)
if mUpd > ops[i].x {
fmt.Println("NO")
return
}
if mUpd < ops[i].x {
mUnupd, mIdx := queryMaxUnupd(1, 1, n, ops[i].l, ops[i].r)
if mUnupd < ops[i].x {
fmt.Println("NO")
return
}
required[mIdx] = true
a[mIdx] = ops[i].x
}
} else {
updateUpd(1, 1, n, ops[i].k, ops[i].d)
updateUnupd(1, 1, n, ops[i].k, -1)
}
}
for k := 1; k <= n; k++ {
if !required[k] {
a[k] = limit[k]
}
}
counts := make([]int, 30)
for k := 1; k <= n; k++ {
for p := 0; p < 30; p++ {
if (a[k]>>p)&1 == 1 {
counts[p]++
}
}
}
for p := 29; p >= 0; p-- {
if counts[p] > 1 {
changed := false
for k := 1; k <= n; k++ {
if !required[k] && ((a[k]>>p)&1 == 1) {
a[k] = (a[k] ^ (1 << p)) | ((1 << p) - 1)
changed = true
break
}
}
if changed {
break
}
}
}
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
fmt.Fprintln(out, "YES")
for k := 1; k <= n; k++ {
fmt.Fprintf(out, "%d ", a[k])
}
fmt.Fprintln(out)
}