← Home
For problem statement at 1000-1999/1100-1199/1180-1189/1186/problemE.txt this is a correct solution, but verifier at 1000-1999/1100-1199/1180-1189/1186/verifierE.go ends with All 100 tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math/bits"
	"os"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Buffer(make([]byte, 1024*1024), 10*1024*1024)
	scanner.Split(bufio.ScanWords)

	scanInt64 := func() int64 {
		scanner.Scan()
		b := scanner.Bytes()
		var res int64
		for _, v := range b {
			res = res*10 + int64(v-'0')
		}
		return res
	}

	if !scanner.Scan() {
		return
	}
	b := scanner.Bytes()
	var n int64
	for _, v := range b {
		n = n*10 + int64(v-'0')
	}
	m := scanInt64()
	q := scanInt64()

	S := make([][]int64, n+1)
	for i := int64(0); i <= n; i++ {
		S[i] = make([]int64, m+1)
	}

	for i := int64(1); i <= n; i++ {
		scanner.Scan()
		s := scanner.Bytes()
		for j := int64(1); j <= m; j++ {
			val := int64(s[j-1] - '0')
			S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + val
		}
	}

	cntE := func(X int64) int64 {
		if X == 0 {
			return 0
		}
		var even int64 = 0
		var p int = 0
		for i := 60; i >= 0; i-- {
			if (X & (int64(1) << i)) != 0 {
				if i > 0 {
					even += int64(1) << (i - 1)
				} else {
					if p%2 == 0 {
						even += 1
					}
				}
				p++
			}
		}
		return even
	}

	F := func(x, y int64) int64 {
		if x == 0 || y == 0 {
			return 0
		}

		R := x / n
		r := x % n
		C := y / m
		c := y % m

		eR := cntE(R)
		oR := R - eR
		eC := cntE(C)
		oC := C - eC

		var total int64 = 0

		e_RC := eR*eC + oR*oC
		o_RC := eR*oC + oR*eC
		total += e_RC*S[n][m] + o_RC*(n*m - S[n][m])

		if c > 0 {
			pC := bits.OnesCount64(uint64(C)) % 2
			var e_Rc, o_Rc int64
			if pC == 0 {
				e_Rc = eR
				o_Rc = oR
			} else {
				e_Rc = oR
				o_Rc = eR
			}
			total += e_Rc*S[n][c] + o_Rc*(n*c - S[n][c])
		}

		if r > 0 {
			pR := bits.OnesCount64(uint64(R)) % 2
			var e_rC, o_rC int64
			if pR == 0 {
				e_rC = eC
				o_rC = oC
			} else {
				e_rC = oC
				o_rC = eC
			}
			total += e_rC*S[r][m] + o_rC*(r*m - S[r][m])
		}

		if r > 0 && c > 0 {
			pRC := (bits.OnesCount64(uint64(R)) + bits.OnesCount64(uint64(C))) % 2
			if pRC == 0 {
				total += S[r][c]
			} else {
				total += r*c - S[r][c]
			}
		}

		return total
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	for i := int64(0); i < q; i++ {
		x1 := scanInt64()
		y1 := scanInt64()
		x2 := scanInt64()
		y2 := scanInt64()

		ans := F(x2, y2) - F(x1-1, y2) - F(x2, y1-1) + F(x1-1, y1-1)
		fmt.Fprintln(out, ans)
	}
}