← Home
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)
}