結果

問題 No.1000 Point Add and Array Add
ユーザー ccppjsrbccppjsrb
提出日時 2020-09-29 10:48:34
言語 Go
(1.22.1)
結果
AC  
実行時間 660 ms / 2,000 ms
コード長 7,467 bytes
コンパイル時間 10,848 ms
コンパイル使用メモリ 220,348 KB
実行使用メモリ 50,560 KB
最終ジャッジ日時 2024-07-03 15:32:08
合計ジャッジ時間 17,213 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 1 ms
6,948 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 3 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 5 ms
6,940 KB
testcase_15 AC 4 ms
6,944 KB
testcase_16 AC 413 ms
35,584 KB
testcase_17 AC 355 ms
24,448 KB
testcase_18 AC 660 ms
41,472 KB
testcase_19 AC 611 ms
41,472 KB
testcase_20 AC 527 ms
50,560 KB
testcase_21 AC 502 ms
36,632 KB
testcase_22 AC 529 ms
46,848 KB
testcase_23 AC 550 ms
35,072 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	q := getNextInt(scanner)
	aa := make([]int, n)
	seg := NewLazySegTree(n, E, ID)
	for i := 0; i < n; i++ {
		aa[i] = getNextInt(scanner)
	}
	ss := make([]int, n+1)
	add := make([][3]int, 0)
	for q > 0 {
		q--
		c := getNextString(scanner)
		x := getNextInt(scanner) - 1
		y := getNextInt(scanner)
		if c == "A" {
			add = append(add, [3]int{x, y, seg.Prod(x, x+1).(*S).x})
			continue
		}
		seg.ApplyRange(x, y, &F{x: 1})
		ss[x]++
		ss[y]--
	}
	bb := make([]int, n)
	for i := 0; i < n; i++ {
		ss[i+1] += ss[i]
	}
	for i := 0; i < n; i++ {
		bb[i] += aa[i] * ss[i]
	}
	for _, p := range add {
		bb[p[0]] += p[1] * (ss[p[0]] - p[2])
	}
	sep := ""
	for i := 0; i < n; i++ {
		fmt.Fprintf(writer, "%s%d", sep, bb[i])
		sep = " "
	}
	fmt.Fprintln(writer, "")
}

type S struct {
	x int
}

func (s *S) Op(l, r SInterface) SInterface {
	ll, rr := l.(*S), r.(*S)
	s.x = ll.x + rr.x
	return s
}
func (s *S) Mapping(l FInterface, r SInterface) SInterface {
	ll, rr := l.(*F), r.(*S)
	s.x = rr.x + ll.x
	return s
}
func (s *S) E() {
	s.x = 0
}
func E() SInterface {
	var s S
	s.E()
	return &s
}

type F struct {
	x int
}

func (f *F) Composition(l, r FInterface) FInterface {
	ll, rr := l.(*F), r.(*F)
	f.x = ll.x + rr.x
	return f
}
func (f *F) ID() {
	f.x = 0
}
func ID() FInterface {
	var f F
	f.ID()
	return &f
}

// SInterface Type S interface
type SInterface interface {
	Op(SInterface, SInterface) SInterface
	Mapping(FInterface, SInterface) SInterface
	E()
}

// FInterface Type F interface
type FInterface interface {
	Composition(FInterface, FInterface) FInterface
	ID()
}

// LazySegTree is the data structure for monoids
type LazySegTree struct {
	n, size, log int
	e            func() SInterface
	id           func() FInterface
	d            []SInterface
	lz           []FInterface
	sml, smr     SInterface
}

// NewLazySegTree Constructor
func NewLazySegTree(n int, e func() SInterface, id func() FInterface) *LazySegTree {
	a := make([]SInterface, n)
	for i := 0; i < n; i++ {
		a[i] = e()
	}
	return NewLazySegTreeWithData(a, e, id)
}

// NewLazySegTreeWithData Constructor
func NewLazySegTreeWithData(a []SInterface, e func() SInterface, id func() FInterface) *LazySegTree {
	n := len(a)
	log := 0
	for i := n; i > 0; i >>= 1 {
		log++
	}
	size := 1 << log
	d := make([]SInterface, size<<1)
	lz := make([]FInterface, size)
	for i := 0; i < size<<1; i++ {
		d[i] = e()
	}
	for i := 0; i < size; i++ {
		lz[i] = id()
	}
	for i := 0; i < n; i++ {
		d[i+size] = a[i]
	}
	s := LazySegTree{d: d, lz: lz, n: n, size: size, log: log, e: e, id: id, sml: e(), smr: e()}
	for i := size - 1; i > 0; i-- {
		s.update(i)
	}
	return &s
}

// Set assigns x to a[p]
func (s *LazySegTree) Set(p int, x SInterface) {
	p += s.size
	for i := s.log; i > 0; i-- {
		s.push(p >> i)
	}
	s.d[p] = x
	for i := 1; i <= s.log; i++ {
		s.update(p >> i)
	}
}

// Get returns a[p]
func (s *LazySegTree) Get(p int) SInterface {
	p += s.size
	for i := s.log; i > 0; i-- {
		s.push(p >> i)
	}
	return s.d[p]
}

// Prod returns op(a[l], ..., a[r - 1]), assuming the properties of the monoid. It returns e() if l = r.
func (s *LazySegTree) Prod(l, r int) SInterface {
	if l >= r {
		return s.e()
	}
	s.sml.E()
	s.smr.E()
	l += s.size
	r += s.size
	for i := s.log; i > 0; i-- {
		if (l>>i)<<i != l {
			s.push(l >> i)
		}
		if (r>>i)<<i != r {
			s.push(r >> i)
		}
	}
	for l < r {
		if l&1 == 1 {
			s.sml.Op(s.sml, s.d[l])
			l++
		}
		if r&1 == 1 {
			r--
			s.smr.Op(s.d[r], s.smr)
		}
		l >>= 1
		r >>= 1
	}
	return s.sml.Op(s.sml, s.smr)
}

// AllProd returns op(a[0], ..., a[n - 1]), assuming the properties of the monoid. It returns e() if n = 0.
func (s *LazySegTree) AllProd() SInterface {
	return s.d[1]
}

// Apply applies a[p] = op_st(a[p], x).
func (s *LazySegTree) Apply(p int, f FInterface) {
	p += s.size
	for i := s.log; i > 0; i-- {
		s.push(p >> i)
	}
	s.d[p].Mapping(f, s.d[p])
	for i := 1; i <= s.log; i++ {
		s.update(p >> i)
	}
}

// ApplyRange applies a[p] = op_st(a[p], x) for all i = l..r-1.
func (s *LazySegTree) ApplyRange(l, r int, f FInterface) {
	if l == r {
		return
	}
	l += s.size
	r += s.size
	for i := s.log; i > 0; i-- {
		if (l>>i)<<i != l {
			s.push(l >> i)
		}
		if (r>>i)<<i != r {
			s.push(r >> i)
		}
	}
	ll := l
	rr := r
	for l < r {
		if l&1 == 1 {
			s.allApply(l, f)
			l++
		}
		if r&1 == 1 {
			r--
			s.allApply(r, f)
		}
		l >>= 1
		r >>= 1
	}
	l = ll
	r = rr
	for i := 1; i <= s.log; i++ {
		if (l>>i)<<i != l {
			s.update(l >> i)
		}
		if (r>>i)<<i != r {
			s.update(r >> i)
		}
	}
}

// MaxRight returns an index r that satisfies both of the following.
// r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
// r = n or f(op(a[l], a[l + 1], ..., a[r])) = false
func (s *LazySegTree) MaxRight(l int, f func(x SInterface) bool) int {
	if l == s.n {
		return s.n
	}
	l += s.size
	for i := s.log; i > 0; i-- {
		s.push(l >> uint(i))
	}
	s.sml.E()
	s.smr.E()
	for {
		for l&1 == 0 {
			l >>= 1
		}
		if !f(s.smr.Op(s.sml, s.d[l])) {
			for l < s.size {
				s.push(l)
				l <<= 1
				if f(s.smr.Op(s.sml, s.d[l])) {
					s.sml, s.smr = s.smr, s.sml
					l++
				}
			}
			return l - s.size
		}
		s.sml.Op(s.sml, s.d[l])
		l++
		if l&-l == l {
			break
		}
	}
	return s.n
}

// MinLeft returns an index l that satisfies both of the following.
// l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true
// l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false
func (s *LazySegTree) MinLeft(r int, f func(x SInterface) bool) int {
	if r == 0 {
		return 0
	}
	r += s.size
	for i := s.log; i > 0; i-- {
		s.push((r - 1) >> uint(i))
	}
	s.sml.E()
	s.smr.E()
	for {
		r--
		for r > 1 && r&1 == 1 {
			r >>= 1
		}
		if !f(s.smr.Op(s.sml, s.d[r])) {
			for r < s.size {
				s.push(r)
				r = r<<1 + 1
				if f(s.smr.Op(s.sml, s.d[r])) {
					s.sml, s.smr = s.smr, s.sml
					r--
				}
			}
			return r + 1 - s.size
		}
		s.sml.Op(s.sml, s.d[r])
		if r&-r == r {
			break
		}
	}
	return 0
}
func (s *LazySegTree) update(k int) {
	s.d[k].Op(s.d[k<<1], s.d[k<<1+1])
}
func (s *LazySegTree) allApply(k int, f FInterface) {
	s.d[k].Mapping(f, s.d[k])
	if k < s.size {
		s.lz[k].Composition(f, s.lz[k])
	}
}
func (s *LazySegTree) push(k int) {
	s.allApply(k<<1, s.lz[k])
	s.allApply(k<<1+1, s.lz[k])
	s.lz[k].ID()
}
0