• DMOJ
  • Trang chủ
  • Bài tập
  • Bài nộp
  • Thành viên
  • Kỳ thi
  • Chat
  • Giới thiệu
    • Máy chấm

Tiếng Việt

Tiếng Việt
English

Đăng nhập

Đăng ký

luonghuubaohb2

  • Giới thiệu
  • Bài tập
  • Bài nộp

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()


«    »
Thứ 2
Thứ 3
Thứ 4
Thứ 5
Thứ 6
Thứ 7
CN
Ít
Nhiều

Bkis Academy Online Judge | Powered by DMOJ | © 2025 Bkis Academy