結果

問題 No.3325 陰陽師
コンテスト
ユーザー ID 21712
提出日時 2025-12-30 01:32:21
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 1,543 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 14,268 ms
コンパイル使用メモリ 244,728 KB
実行使用メモリ 22,748 KB
最終ジャッジ日時 2025-12-30 01:32:48
合計ジャッジ時間 25,146 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"
import . "os"
import bf "bufio"
import . "sort"

func main() {
	rd:=bf.NewReader(Stdin)
	var n,m int
	Fscan(rd,&n,&m)
	ss := make([]int, n)
	for i:=range ss{
		Fscan(rd,&ss[i])
	}
	ts := make([]int, n)
	for i:=range ts{
		Fscan(rd,&ts[i])
	}
	Ints(ss)
	tree := gen(ss)
	zs := make([]int, 0, m)
	for _, t := range ts {
		_, ok := tree.Get(t) // TLEしそう
		if ok {
			zs = append(zs, t)
		} else {
			break
		}
	}
	Ints(zs)
	ans := 0
	for _, z := range zs {
		for len(ss) > 0 && ss[0] < z {
			ss = ss[1:]
		}
		if len(ss) == 0 {
			panic("bug")
		}
		ans = max(ans, ss[0]-z)
	}
	Println(ans)
}

type Node struct {
	value,count,total int
	left,right *Node
}

func (node*Node) Total() int {
	if node == nil {
		return 0
	}
	return node.total
}

func gen(xs []int) *Node {
	if len(xs) == 0 {
		return nil
	}
	lp := len(xs)/2
	value := xs[lp]
	count := 1
	for lp > 0 {
		if xs[lp-1] != value {
			break
		}
		count++
		lp--
	}
	rp := len(xs)/2
	for rp+1<len(xs) {
		if xs[rp+1] != value {
			break
		}
		count++
		rp++
	}
	left := gen(xs[:lp])
	right := gen(xs[rp+1:])
	total := count+left.Total()+right.Total()
	return &Node{value,count,total,left,right}
}

func (node *Node)Get(x int) (ret int, ok bool) {
	if node.Total() == 0 {
		return
	}
	if x < node.value {
		ret, ok = node.left.Get(x)
		if ok {
			node.total--
			return
		}
	}
	if x <= node.value && node.count > 0 {
		ret = node.value
		node.count--
		node.total--
		ok = true
		return
	}
	ret, ok = node.right.Get(x)
	if ok {
		node.total--
	}
	return
}
0