結果
| 問題 |
No.871 かえるのうた
|
| コンテスト | |
| ユーザー |
 kohei2019
|
| 提出日時 | 2022-05-04 14:38:52 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,796 bytes |
| コンパイル時間 | 147 ms |
| コンパイル使用メモリ | 82,472 KB |
| 実行使用メモリ | 107,044 KB |
| 最終ジャッジ日時 | 2024-07-03 17:19:14 |
| 合計ジャッジ時間 | 7,970 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 18 WA * 31 |
ソースコード
#非再帰の平衡二分木
import copy
class Node:
"""ノード
Attributes:
key (any): ノードのキー。比較可能なものであれば良い。(1, 4)などタプルも可。
val (any): ノードの値。
lch (Node): 左の子ノード。
rch (Node): 右の子ノード。
bias (int): 平衡度。(左部分木の高さ)-(右部分木の高さ)。
size (int): 自分を根とする部分木の大きさ
"""
def __init__(self, key, val):
self.key = key
self.val = val
self.lch = None
self.rch = None
self.bias = 0
self.size = 1
class AVLTree:
"""非再帰AVL木
Attributes:
root (Node): 根ノード。初期値はNone。
valdefault (any): ノード値のデフォルト値。デフォルトではNone。（数値、リストなど可）
"""
def __init__(self,valdefault=None):
self.root = None
self.valdefault = valdefault
def rotate_left(self, v):
u = v.rch
u.size = v.size
v.size -= u.rch.size + 1 if u.rch is not None else 1
v.rch = u.lch
u.lch = v
if u.bias == -1:
u.bias = v.bias = 0
else:
u.bias = 1
v.bias = -1
return u
def rotate_right(self, v):
u = v.lch
u.size = v.size
v.size -= u.lch.size + 1 if u.lch is not None else 1
v.lch = u.rch
u.rch = v
if u.bias == 1:
u.bias = v.bias = 0
else:
u.bias = -1
v.bias = 1
return u
def rotateLR(self, v):
u = v.lch
t = u.rch
t.size = v.size
v.size -= u.size - (t.rch.size if t.rch is not None else 0)
u.size -= t.rch.size + 1 if t.rch is not None else 1
u.rch = t.lch
t.lch = u
v.lch = t.rch
t.rch = v
self.update_bias_double(t)
return t
def rotateRL(self, v):
u = v.rch
t = u.lch
t.size = v.size
v.size -= u.size - (t.lch.size if t.lch is not None else 0)
u.size -= t.lch.size + 1 if t.lch is not None else 1
u.lch = t.rch
t.rch = u
v.rch = t.lch
t.lch = v
self.update_bias_double(t)
return t
def update_bias_double(self, v):
if v.bias == 1:
v.rch.bias = -1
v.lch.bias = 0
elif v.bias == -1:
v.rch.bias = 0
v.lch.bias = 1
else:
v.rch.bias = 0
v.lch.bias = 0
v.bias = 0
def insert(self, key, val=None):
"""挿入
指定したkeyを挿入する。valはkeyのノード値。
Args:
key (any): キー。
val (any): 値。（指定しない場合はvaldefaultが入る）
Note:
同じキーがあった場合は上書きする。
"""
if val == None:
val = copy.deepcopy(self.valdefault)
if self.root is None:
self.root = Node(key, val)
return
v = self.root
history = []
while v is not None:
if key < v.key:
history.append((v, 1))
v = v.lch
elif v.key < key:
history.append((v, -1))
v = v.rch
elif v.key == key:
v.val = val
return
p, pdir = history[-1]
if pdir == 1:
p.lch = Node(key, val)
else:
p.rch = Node(key, val)
while history:
v, direction = history.pop()
v.bias += direction
v.size += 1
new_v = None
b = v.bias
if b == 0:
break
if b == 2:
u = v.lch
if u.bias == -1:
new_v = self.rotateLR(v)
else:
new_v = self.rotate_right(v)
break
if b == -2:
u = v.rch
if u.bias == 1:
new_v = self.rotateRL(v)
else:
new_v = self.rotate_left(v)
break
if new_v is not None:
if len(history) == 0:
self.root = new_v
return
p, pdir = history.pop()
p.size += 1
if pdir == 1:
p.lch = new_v
else:
p.rch = new_v
while history:
p, pdir = history.pop()
p.size += 1
def delete(self, key):
"""削除
指定したkeyの要素を削除する。
Args:
key (any): キー。
Return:
bool: 指定したキーが存在するならTrue、しないならFalse。
"""
v = self.root
history = []
while v is not None:
if key < v.key:
history.append((v, 1))
v = v.lch
elif v.key < key:
history.append((v, -1))
v = v.rch
else:
break
else:
return False
if v.lch is not None:
history.append((v, 1))
lmax = v.lch
while lmax.rch is not None:
history.append((lmax, -1))
lmax = lmax.rch
v.key = lmax.key
v.val = lmax.val
v = lmax
c = v.rch if v.lch is None else v.lch
if history:
p, pdir = history[-1]
if pdir == 1:
p.lch = c
else:
p.rch = c
else:
self.root = c
return True
while history:
new_p = None
p, pdir = history.pop()
p.bias -= pdir
p.size -= 1
b = p.bias
if b == 2:
if p.lch.bias == -1:
new_p = self.rotateLR(p)
else:
new_p = self.rotate_right(p)
elif b == -2:
if p.rch.bias == 1:
new_p = self.rotateRL(p)
else:
new_p = self.rotate_left(p)
elif b != 0:
break
if new_p is not None:
if len(history) == 0:
self.root = new_p
return True
gp, gpdir = history[-1]
if gpdir == 1:
gp.lch = new_p
else:
gp.rch = new_p
if new_p.bias != 0:
break
while history:
p, pdir = history.pop()
p.size -= 1
return True
def member(self, key):
"""キーの存在チェック
指定したkeyがあるかどうか判定する。
Args:
key (any): キー。
Return:
bool: 指定したキーが存在するならTrue、しないならFalse。
"""
v = self.root
while v is not None:
if key < v.key:
v = v.lch
elif v.key < key:
v = v.rch
else:
return True
return False
def getval(self, key):
"""値の取り出し
指定したkeyの値を返す。
Args:
key (any): キー。
Return:
any: 指定したキーが存在するならそのオブジェクト。存在しなければvaldefault
"""
v = self.root
while v is not None:
if key < v.key:
v = v.lch
elif v.key < key:
v = v.rch
else:
return v.val
self.insert(key)
return self[key] #
def lower_bound(self, key):
"""下限つき探索
指定したkey以上で最小のキーを見つける。[key,inf)で最小
Args:
key (any): キーの下限。
Return:
any: 条件を満たすようなキー。そのようなキーが一つも存在しないならNone。
"""
ret = None
v = self.root
while v is not None:
if v.key >= key:
if ret is None or ret > v.key:
ret = v.key
v = v.lch
else:
v = v.rch
return ret
def upper_bound(self, key):
"""上限つき探索
指定したkey未満で最大のキーを見つける。[-inf,key)で最大
Args:
key (any): キーの上限。
Return:
any: 条件を満たすようなキー。そのようなキーが一つも存在しないならNone。
"""
ret = None
v = self.root
while v is not None:
if v.key < key:
if ret is None or ret < v.key:
ret = v.key
v = v.rch
else:
v = v.lch
return ret
def find_kth_element(self, k):
"""小さい方からk番目の要素を見つける
Args:
k (int): 何番目の要素か(0オリジン)。
Return:
any: 小さい方からk番目のキーの値。
"""
v = self.root
s = 0
while v is not None:
t = s+v.lch.size if v.lch is not None else s
if t == k:
return v.key
elif t < k:
s = t+1
v = v.rch
else:
v = v.lch
return None
def key_kth(self,key):
'''
Args:
keyが何番目に小さい要素かを調べる
Return:
int(keyが存在しなければNone)
'''
v = self.root
kth = 0
f = False
while v is not None:
if key < v.key:
v = v.lch
elif v.key < key:
kth += 1+v.lch.size if v.lch is not None else 1
v = v.rch
else:
kth += v.lch.size if v.lch is not None else 0
f = True
break
if f:
return kth
else:
return None
def getmin(self):
'''
Return:
any: 存在するキーの最小値
'''
if len(self) == 0:
raise('empty')
ret = None
v = self.root
while True:
ret = v
v = v.lch
if v == None:
break
return ret.key
def getmax(self):
'''
Return:
any: 存在するキーの最大値
'''
if len(self) == 0:
raise('empty')
ret = None
v = self.root
while True:
ret = v
v = v.rch
if v == None:
break
return ret.key
def popmin(self):
'''
存在するキーの最小値をpopする
Return:
any: popした値
'''
if len(self) == 0:
raise('empty')
ret = None
v = self.root
while True:
ret = v
v = v.lch
if v == None:
break
del self[ret.key]
return ret.key
def popmax(self):
'''
存在するキーの最大値をpopする
Return:
any: popした値
'''
if len(self) == 0:
raise('empty')
ret = None
v = self.root
while True:
ret = v
v = v.rch
if v == None:
break
del self[ret.key]
return ret.key
def popkth(self,k):
'''
存在するキーの小さい方からk番目をpopする
Return:
any: popした値
'''
key = self.find_kth_element(k)
del self[key]
return key
def get_key_val(self):
'''
Return:
dict: 存在するキーとノード値をdictで出力
'''
retdict = dict()
for i in range(len(self)):
key = self.find_kth_element(i)
val = self[key]
retdict[key] = val
return retdict
def values(self):
for i in range(len(self)):
yield self[self.find_kth_element(i)]
def keys(self):
for i in range(len(self)):
yield self.find_kth_element(i)
def items(self):
for i in range(len(self)):
key = self.find_kth_element(i)
yield key,self[key]
def __iter__(self): return self.keys()
def __contains__(self, key): return self.member(key)
def __getitem__(self, key): return self.getval(key)
def __setitem__(self, key, val): return self.insert(key, val)
def __delitem__(self, key): return self.delete(key)
def __bool__(self): return self.root is not None
def __len__(self): return self.root.size if self.root is not None else 0
def __str__(self): return str(type(self))+'('+str(self.get_key_val())+')'
N,K = map(int,input().split())
lsX = list(map(int,input().split()))
lsA = list(map(int,input().split()))
AT = AVLTree()
for i in range(N):
AT.insert((lsX[i],i))
f = True
l,r = lsX[K-1]-lsA[K-1],lsX[K-1]+lsA[K-1]
ans = 1
AT.delete((lsX[K-1],K-1))
while f:
ln,rn = l,r
while AT.lower_bound((l,0)) != None and AT.lower_bound((l,0)) <=(r,N+1):
k = AT.lower_bound((l,0))
ln = min(ln,k[0]-lsA[k[1]])
rn = min(ln,k[0]+lsA[k[1]])
AT.delete(k)
ans += 1
if ln == l and rn == r:
break
print(ans)