結果

問題 No.610 区間賞(Section Award)
ユーザー tktk_snsn
提出日時 2022-02-13 01:49:41
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 741 ms / 2,000 ms
コード長 797 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 56,392 KB
最終ジャッジ日時 2024-06-29 05:19:28
合計ジャッジ時間 14,290 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #

from collections import deque

N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))
B = list(map(lambda x: int(x) - 1, input().split()))
atoi = [-1] * N
btoi = [-1] * N
for i, a in enumerate(A):
    atoi[a] = i
for i, b in enumerate(B):
    btoi[b] = i

task = []
for i in range(N):
    s = atoi[i]
    t = btoi[i]
    if s >= t:
        i += 1
        task.append((s, i))
        task.append((t, -i))
task.sort(reverse=True)

que = deque()
ans = []
seen = set()
for _, x in task:
    if x > 0:
        que.append(x)
    else:
        x = -x
        seen.add(x)
        if que[0] == x:
            ans.append(x)
            que.popleft()
    while que and que[0] in seen:
        que.popleft()
    while que and que[-1] in seen:
        que.pop()

ans.sort()
print(*ans, sep="\n")
0