結果

問題 No.1435 Mmm......
コンテスト
ユーザー sgsw
提出日時 2021-08-15 01:52:37
言語 Go
(1.23.4)
結果
AC  
実行時間 760 ms / 2,000 ms
コード長 5,009 bytes
コンパイル時間 11,377 ms
コンパイル使用メモリ 229,452 KB
実行使用メモリ 96,664 KB
最終ジャッジ日時 2024-10-06 07:52:20
合計ジャッジ時間 22,431 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

/*
    library test

*/

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
}
0