#690079 (Go) No.1435 Mmm......

提出ソース

結果

問題	No.1435 Mmm......
ユーザー	sgsw
提出日時	2021-08-15 01:43:50
言語	Go (1.22.1)
結果	AC
実行時間	789 ms / 2,000 ms
コード長	5,100 bytes
コンパイル時間	15,743 ms
コンパイル使用メモリ	224,268 KB
実行使用メモリ	93,968 KB
最終ジャッジ日時	2024-04-16 00:04:54
合計ジャッジ時間	27,106 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	1 ms 6,940 KB
testcase_06	AC	351 ms 75,844 KB
testcase_07	AC	407 ms 78,424 KB
testcase_08	AC	469 ms 88,280 KB
testcase_09	AC	431 ms 86,232 KB
testcase_10	AC	392 ms 83,032 KB
testcase_11	AC	380 ms 79,444 KB
testcase_12	AC	355 ms 73,436 KB
testcase_13	AC	349 ms 75,488 KB
testcase_14	AC	252 ms 45,784 KB
testcase_15	AC	470 ms 88,540 KB
testcase_16	AC	405 ms 80,328 KB
testcase_17	AC	261 ms 46,420 KB
testcase_18	AC	485 ms 89,088 KB
testcase_19	AC	385 ms 77,644 KB
testcase_20	AC	450 ms 82,460 KB
testcase_21	AC	642 ms 89,552 KB
testcase_22	AC	789 ms 93,968 KB
testcase_23	AC	498 ms 90,324 KB
testcase_24	AC	488 ms 90,584 KB
testcase_25	AC	489 ms 91,096 KB
testcase_26	AC	494 ms 91,480 KB
testcase_27	AC	494 ms 90,588 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package main

/*
	Go-Lang(1.16) Template for Programming-Contest.

	author : sgsw

	generated : 2021/08/15
	when : 01:16:51

*/

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

var wg = bufio.NewScanner(os.Stdin)

const (
	inf            = int(1e18)
	initialBufSize = int(1e6)
	maxBufSize     = int(1e6)
)

var buf []byte = make([]byte, initialBufSize)

type monoid struct {
	first, second int
	max           int
}

func (x monoid) Get() interface{} {
	return x
}

func (x monoid) Ide() Monoid {
	return monoid{first: inf, second: inf, max: -inf}
}

func (x monoid) Op(z Monoid) Monoid {
	y := z.(monoid)
	minval := x.max
	if y.max > minval {
		minval = y.max
	}
	if x.first <= y.first {
		if x.second < y.first {
			return monoid{x.first, x.second, minval}
		} else {
			return monoid{x.first, y.first, minval}
		}
	} else {
		if y.second < x.first {
			return monoid{y.first, y.second, minval}
		} else {
			return monoid{y.first, x.first, minval}
		}
	}
}

func main() {
	n := nextInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
	}

	seg, _ := Gen(monoid{}, n)
	b := make([]Monoid, n)
	for i := 0; i < n; i++ {
		b[i] = monoid{a[i], inf, a[i]}
	}
	_ = SliceGen(seg, b)

	question := func(m Monoid) bool {
		M := m.(monoid)
		return M.first+M.second >= M.max
	}

	ans := 0
	for l := 0; l < n; l++ {
		r := seg.MaxRight(l, question)
		if l == r {
			continue
		}
		ans += r - l - 1
		// fmt.Println(l, r)
	}
	fmt.Printf("%d\n", ans)
}

// greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

func init() {
	wg.Split(bufio.ScanWords)
	wg.Buffer(buf, maxBufSize)
}

func nextInt() int {
	wg.Scan()
	i, e := strconv.Atoi(wg.Text())
	if e != nil {
		panic(e)
	}
	return i
}

/*
Monoid-Structure should be decleared some-where else.
-> op(Monoid,Monoid)Monoid & ide()Monoid is required.
*/

type Monoid interface {
	Get() interface{}
	Op(Monoid) Monoid
	Ide() Monoid
}

type SegTree struct {
	monoid_type Monoid
	op          func(Monoid) Monoid /* op */
	e           func() Monoid       /*identity*/
	d           []Monoid
	_d          []Monoid
	n           int /* size*/
	log         int
	size        int
}

func Gen(monoid Monoid, n int) (SegTree, bool) {

	seg := SegTree{monoid_type: monoid, op: monoid.Op, e: monoid.Ide, d: []Monoid{}, _d: []Monoid{}, n: 0, log: 0, size: 0}
	collect := true

	switch n > 0 {
	case true:
		seg.d = make([]Monoid, n)
		for i := range seg.d {
			seg.d[i] = seg.e()
		}
	default:
		collect = false
		return seg, collect
	}

	seg.n = len(seg.d)
	for ord := 0; (1 << ord) < seg.n; {
		ord++
		seg.log = ord
	}

	seg.size = 1 << seg.log
	seg._d = make([]Monoid, 2*seg.size)
	for i := range seg._d {
		seg._d[i] = seg.e()
	}

	for i := 0; i < seg.n; i++ {
		seg._d[seg.size+i] = seg.d[i]
	}
	for i := seg.size - 1; i > 0; i-- {
		seg._update(i)
	}
	return seg, collect
}

func SliceGen(seg SegTree, array []Monoid) bool {
	ok := true
	if len(array) != seg.n {
		ok = false
		return ok
	}

	for _, v := range array {
		if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) {
			ok = false
			return ok
		}
	}

	for i, v := range array {
		seg.Set(i, v)
	}

	for i := seg.size - 1; i > 0; i-- {
		seg._update(i)
	}

	return ok
}

func (seg SegTree) _update(k int) {
	seg._d[k] = seg._d[2*k].Op(seg._d[2*k+1])
}

func (seg SegTree) Set(p int, x Monoid) {
	//a[p] -> x
	p += seg.size
	seg._d[p] = x
	for i := 1; i <= seg.log; i++ {
		seg._update(p >> i)
	}
}

func (seg SegTree) Get(p int) Monoid {
	// a[p]
	return seg._d[p+seg.size]
}

func (seg SegTree) OverWrite(p int, f func(Monoid) Monoid) {
	p += seg.size
	m := seg._d[p]
	seg._d[p] = f(m)
	for i := 1; i <= seg.log; i++ {
		seg._update(p >> i)
	}
}

func (seg SegTree) Prod(l, r int) Monoid {
	//op(a[l..r))
	sml := seg.e()
	smr := seg.e()
	l += seg.size
	r += seg.size
	for l < r {
		if l&1 == 1 {
			sml = sml.Op(seg._d[l])
			l++
		}
		if r&1 == 1 {
			r--
			smr = seg._d[r].Op(smr)
		}
		l >>= 1
		r >>= 1
	}
	return sml.Op(smr)
}

func (seg SegTree) AllProd() Monoid {
	return seg._d[1]
}

func (seg SegTree) MaxRight(left int, f func(Monoid) bool) int {
	if left == seg.n {
		return seg.n
	}
	left += seg.size
	sm := seg.e()
	first := true

	for first || (left&(-left)) != left {
		first = false
		for left&1 == 0 {
			left >>= 1
		}
		if !f(sm.Op(seg._d[left])) {
			for left < seg.size {
				left <<= 1
				if f(sm.Op(seg._d[left])) {
					sm = sm.Op(seg._d[left])
					left++
				}
			}
			return left - seg.size
		}
		sm = sm.Op(seg._d[left])
		left++
	}
	return seg.n
}

func (seg SegTree) MinLeft(right int, f func(Monoid) bool) int {
	if right == 0 {
		return 0
	}
	right += seg.size
	sm := seg.e()
	first := true

	for first || (right&(-right)) != right {
		first = false
		right--
		for right > 1 && right&1 == 0 {
			right >>= 1
		}
		if !f(sm.Op(seg._d[right])) {
			for right < seg.size {
				right = right*2 + 1
				if f(sm.Op(seg._d[right])) {
					sm = sm.Op((seg._d[right]))
					right--
				}
			}
			return right + 1 - seg.size
		}
		sm = sm.Op(seg._d[right])
	}
	return 0
}

yukicoder

結果

テストケース

ソースコード