#690526 (Go) No.1332 Range Nearest Query

提出ソース

結果

問題	No.1332 Range Nearest Query
ユーザー	sgsw
提出日時	2021-08-17 16:22:15
言語	Go (1.22.1)
結果	AC
実行時間	1,432 ms / 2,500 ms
コード長	5,725 bytes
コンパイル時間	16,247 ms
コンパイル使用メモリ	221,408 KB
実行使用メモリ	89,728 KB
最終ジャッジ日時	2024-04-18 21:22:22
合計ジャッジ時間	59,667 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1,267 ms 52,096 KB
testcase_04	AC	1,195 ms 56,192 KB
testcase_05	AC	1,181 ms 56,192 KB
testcase_06	AC	665 ms 68,992 KB
testcase_07	AC	686 ms 68,992 KB
testcase_08	AC	665 ms 68,992 KB
testcase_09	AC	672 ms 68,992 KB
testcase_10	AC	671 ms 68,992 KB
testcase_11	AC	689 ms 85,888 KB
testcase_12	AC	687 ms 85,504 KB
testcase_13	AC	689 ms 85,888 KB
testcase_14	AC	687 ms 85,888 KB
testcase_15	AC	693 ms 85,888 KB
testcase_16	AC	1,402 ms 86,400 KB
testcase_17	AC	1,399 ms 87,936 KB
testcase_18	AC	1,382 ms 85,888 KB
testcase_19	AC	1,402 ms 85,888 KB
testcase_20	AC	1,382 ms 87,936 KB
testcase_21	AC	1,389 ms 87,424 KB
testcase_22	AC	1,399 ms 87,936 KB
testcase_23	AC	1,407 ms 89,728 KB
testcase_24	AC	1,432 ms 85,888 KB
testcase_25	AC	1,423 ms 87,936 KB
testcase_26	AC	571 ms 70,272 KB
testcase_27	AC	552 ms 64,256 KB
testcase_28	AC	196 ms 7,936 KB
testcase_29	AC	198 ms 7,808 KB
testcase_30	AC	194 ms 7,936 KB
testcase_31	AC	190 ms 7,808 KB
testcase_32	AC	197 ms 7,936 KB
testcase_33	AC	196 ms 8,064 KB
testcase_34	AC	191 ms 7,680 KB
testcase_35	AC	194 ms 7,936 KB
testcase_36	AC	188 ms 8,064 KB
testcase_37	AC	197 ms 7,808 KB
testcase_38	AC	915 ms 51,968 KB
testcase_39	AC	318 ms 15,232 KB
testcase_40	AC	1,352 ms 85,248 KB
testcase_41	AC	455 ms 24,192 KB
testcase_42	AC	785 ms 49,280 KB
testcase_43	AC	592 ms 34,304 KB
testcase_44	AC	1,078 ms 60,672 KB
testcase_45	AC	947 ms 58,112 KB
testcase_46	AC	695 ms 35,840 KB
testcase_47	AC	883 ms 55,808 KB

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

ソースコード

raw source code

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"

	"reflect"
)

var wg = bufio.NewScanner(os.Stdin)

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

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

//区間最小をとるモノイド
type min_monoid int

func (x min_monoid) Get() interface{} {
	return x
}
func (x min_monoid) Op(y Monoid) Monoid {
	if int(y.(min_monoid)) < int(x) {
		return y
	} else {
		return x
	}
}
func (x min_monoid) Ide() Monoid {
	return min_monoid(inf)
}

//区間最大をとるモノイド
type max_monoid int

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

func (x max_monoid) Op(y Monoid) Monoid {
	if int(y.(max_monoid)) > int(x) {
		return y
	} else {
		return x
	}
}
func (x max_monoid) Ide() Monoid {
	return max_monoid(-inf)
}

func main() {
	n := nextInt()
	X := make([]struct{ val, idx int }, n)
	for i := 0; i < n; i++ {
		X[i].val = nextInt()
		X[i].idx = i
	}
	q := nextInt()
	Q := make([]struct{ l, r, val, idx int }, q)
	for i := 0; i < q; i++ {
		Q[i].l = nextInt() - 1
		Q[i].r = nextInt()
		Q[i].val = nextInt()
		Q[i].idx = i
	}

	ans := make([]int, q)
	for i := 0; i < q; i++ {
		ans[i] = inf
	}
	//step 1. min_monoid
	sort.Slice(Q, func(i, j int) bool {
		return Q[i].val > Q[j].val
	})
	sort.Slice(X, func(i, j int) bool {
		return X[i].val > X[j].val
	})
	seg, _ := Gen(min_monoid(0), n)
	for itr, i := 0, 0; i < q; i++ {
		for itr < n && X[itr].val >= Q[i].val {
			seg.Set(X[itr].idx, min_monoid(X[itr].val))
			itr++
		}
		val := seg.Prod(Q[i].l, Q[i].r).(min_monoid)
		ans[Q[i].idx] = min(ans[Q[i].idx], int(val)-Q[i].val)
	}

	//step 2.max_monoid
	sort.Slice(Q, func(i, j int) bool {
		return Q[i].val < Q[j].val
	})
	sort.Slice(X, func(i, j int) bool {
		return X[i].val < X[j].val
	})
	seg1, _ := Gen(max_monoid(0), n)
	for itr, i := 0, 0; i < q; i++ {
		for itr < n && X[itr].val < Q[i].val {
			seg1.Set(X[itr].idx, max_monoid(X[itr].val))
			itr++
		}
		val := seg1.Prod(Q[i].l, Q[i].r).(max_monoid)
		ans[Q[i].idx] = min(ans[Q[i].idx], Q[i].val-int(val))
	}
	//step 3.get answer
	for _, v := range ans {
		fmt.Printf("%d\n", v)
	}
}

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

func min(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

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
}

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
}

yukicoder

結果

テストケース

ソースコード