結果
問題 | No.1332 Range Nearest Query |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
package mainimport ("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 intfunc (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 intfunc (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() - 1Q[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_monoidsort.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_monoidsort.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 answerfor _, 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) MonoidIde() Monoid}type SegTree struct {monoid_type Monoidop func(Monoid) Monoid /* op */e func() Monoid /*identity*/d []Monoid_d []Monoidn int /* size*/log intsize 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 := trueswitch n > 0 {case true:seg.d = make([]Monoid, n)for i := range seg.d {seg.d[i] = seg.e()}default:collect = falsereturn seg, collect}seg.n = len(seg.d)for ord := 0; (1 << ord) < seg.n; {ord++seg.log = ord}seg.size = 1 << seg.logseg._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 := trueif len(array) != seg.n {ok = falsereturn ok}for _, v := range array {if reflect.TypeOf(seg.monoid_type) != reflect.TypeOf(v) {ok = falsereturn 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] -> xp += seg.sizeseg._d[p] = xfor 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.sizem := 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.sizer += seg.sizefor 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 >>= 1r >>= 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.sizesm := seg.e()first := truefor first || (left&(-left)) != left {first = falsefor left&1 == 0 {left >>= 1}if !f(sm.Op(seg._d[left])) {for left < seg.size {left <<= 1if 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.sizesm := seg.e()first := truefor first || (right&(-right)) != right {first = falseright--for right > 1 && right&1 == 0 {right >>= 1}if !f(sm.Op(seg._d[right])) {for right < seg.size {right = right*2 + 1if 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}