ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 14446 |
문제명 | Promotion Counting |
레벨 | 플래티넘 3 |
분류 |
구간 쿼리 |
시간복잡도 | O(nlogn) |
인풋사이즈 | n <= 100,000 |
사용한 언어 | Python |
제출기록 | 62272KB / 1132ms |
최고기록 | 1132ms |
해결날짜 | 2021/05/18 |
"""Solution code for "BOJ 14446. Promotion Counting".
- Problem link: https://www.acmicpc.net/problem/14446
- Solution link: http://www.teferi.net/ps/problems/boj/14446
"""
import sys
from teflib import fenwicktree
from teflib import ttree
def main():
N = int(sys.stdin.readline())
p = [int(sys.stdin.readline()) for _ in range(N)]
compressed_p = [None] * N
for i, x in enumerate(sorted(range(N), key=lambda x: p[x])):
compressed_p[x] = i
tree = [[] for _ in range(N)]
for i in range(1, N):
parent = int(sys.stdin.readline())
tree[parent - 1].append(i)
answers = [0] * N
ost = fenwicktree.OrderStatisticTree(N + 1)
root = 0
for node, is_discovering in ttree.dfs(tree, root):
proficiency = compressed_p[node]
if is_discovering:
answers[node] = -(ost.size() - ost.count_less_than(proficiency + 1))
ost.add(proficiency)
else:
answers[node] += ost.size() - ost.count_less_than(proficiency + 1)
print(*answers, sep='\n')
if __name__ == '__main__':
main()