luonghuubaohb2
Rating
-
Bài tập
59
Điểm
1952
Rating #
-
Điểm #
2
huubao_py3 (Archimedes)
Giới thiệu
import sys
input = sys.stdin.read
def solve():
data = input().split()
if not data:
return
n = int(data[0])
a = list(map(int, data[1:n+1]))
m = int(data[n+1])
t = list(map(int, data[n+2:n+2+m]))
a.sort(reverse=True)
tree = [0] * (4 * n)
lazy = [0] * (4 * n)
def build(v, tl, tr):
if tl == tr:
tree[v] = a[tl]
else:
tm = (tl + tr) // 2
build(2 * v, tl, tm)
build(2 * v + 1, tm + 1, tr)
tree[v] = tree[2 * v]
def push(v):
if lazy[v] != 0:
tree[2 * v] -= lazy[v]
lazy[2 * v] += lazy[v]
tree[2 * v + 1] -= lazy[v]
lazy[2 * v + 1] += lazy[v]
lazy[v] = 0
def update(v, tl, tr, l, r):
if l > r:
return
if l == tl and r == tr:
tree[v] -= 1
lazy[v] += 1
else:
push(v)
tm = (tl + tr) // 2
update(2 * v, tl, tm, l, min(r, tm))
update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r)
tree[v] = tree[2 * v]
def query_pos(v, tl, tr, val):
if tree[v] < val:
return -1
if tl == tr:
return tl
push(v)
tm = (tl + tr) // 2
res = query_pos(2 * v + 1, tm + 1, tr, val)
if res == -1:
res = query_pos(2 * v, tl, tm, val)
return res
build(1, 0, n - 1)
out = []
for val in t:
pos = query_pos(1, 0, n - 1, val)
if pos == -1:
out.append("0")
else:
out.append(str(pos + 1))
update(1, 0, n - 1, 0, pos)
sys.stdout.write("\n".join(out) + "\n")
if name == 'main':
solve()
solve()