結果

問題 No.1332 Range Nearest Query
ユーザー sgsw
提出日時 2021-08-17 16:22:15
言語 Go
(1.23.4)
結果
AC  
実行時間 1,386 ms / 2,500 ms
コード長 5,725 bytes
コンパイル時間 13,761 ms
コンパイル使用メモリ 220,988 KB
実行使用メモリ 89,728 KB
最終ジャッジ日時 2024-10-10 14:48:42
合計ジャッジ時間 55,557 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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