← Home
For problem statement at 0-999/900-999/910-919/914/problemF.txt this is a correct solution, but verifier at 0-999/900-999/910-919/914/verifierF.go ends with All tests passed can you fix the verifier? package main

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

type Bitset []uint64

func NewBitset(n int) Bitset {
	return make(Bitset, (n+63)/64)
}

func (b Bitset) Set(i int) {
	b[i/64] |= 1 << (i % 64)
}

func (b Bitset) Clear(i int) {
	b[i/64] &^= 1 << (i % 64)
}

func (b Bitset) Count(l, r int) int {
	if l > r {
		return 0
	}
	startWord := l / 64
	endWord := r / 64
	if startWord == endWord {
		mask := (^uint64(0) >> (63 - (r - l))) << (l % 64)
		return bits.OnesCount64(b[startWord] & mask)
	}

	ans := 0
	mask1 := ^uint64(0) << (l % 64)
	ans += bits.OnesCount64(b[startWord] & mask1)

	for i := startWord + 1; i < endWord; i++ {
		ans += bits.OnesCount64(b[i])
	}

	mask2 := ^uint64(0) >> (63 - (r % 64))
	ans += bits.OnesCount64(b[endWord] & mask2)

	return ans
}

func ShiftLeftAnd(res, b Bitset, words int) {
	var carry uint64 = 0
	for i := 0; i < words; i++ {
		v := res[i]
		res[i] = ((v << 1) | carry) & b[i]
		carry = v >> 63
	}
}

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

	if !scanner.Scan() {
		return
	}
	s := []byte(scanner.Text())
	N := len(s)

	if !scanner.Scan() {
		return
	}
	q, _ := strconv.Atoi(scanner.Text())

	B := make([]Bitset, 26)
	for i := 0; i < 26; i++ {
		B[i] = NewBitset(N)
	}
	for i := 0; i < N; i++ {
		B[s[i]-'a'].Set(i)
	}

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

	for k := 0; k < q; k++ {
		scanner.Scan()
		t := scanner.Text()
		if t == "1" {
			scanner.Scan()
			i, _ := strconv.Atoi(scanner.Text())
			i--
			scanner.Scan()
			c := scanner.Text()[0]
			oldC := s[i]
			if oldC != c {
				B[oldC-'a'].Clear(i)
				B[c-'a'].Set(i)
				s[i] = c
			}
		} else {
			scanner.Scan()
			l, _ := strconv.Atoi(scanner.Text())
			scanner.Scan()
			r, _ := strconv.Atoi(scanner.Text())
			scanner.Scan()
			y := scanner.Text()

			if len(y) > r-l+1 {
				fmt.Fprintln(out, 0)
				continue
			}

			words := (r - 1) / 64 + 1
			copy(res[:words], B[y[0]-'a'][:words])
			for j := 1; j < len(y); j++ {
				ShiftLeftAnd(res, B[y[j]-'a'], words)
			}
			fmt.Fprintln(out, res.Count(l-1+len(y)-1, r-1))
		}
	}
}