マラソンのある区間に関して、$n$ チームのスタート地点での着順とゴール地点での着順が与えられます。
区間賞を取った可能性のあるチームを昇順で全て列挙してください。
・$1 \le n \le 10^{5}$
名作だと思う。典型感が強いのも良い。
---
ゴール地点での着順で見ていき、そのチームがスタート地点で何位だったのかを調べる。
スタート地点での順位が、今までゴール地点での着順で見てきたどのチームのスタート地点での順位よりも悪かったのであれば、
そのチームはものすごい追い上げを見せたことになる。
#!/usr/bin/python2
# -*- coding: utf-8 -*-
# †
n = int(raw_input())
a = map(lambda x: int(x)-1, raw_input().split())
b = map(lambda x: int(x)-1, raw_input().split())
x = [None] * n # x[p] := チーム p のスタート地点での順位
for j, p in enumerate(a):
x[p] = j
maxi = -1
resArr = []
for i, p in enumerate(b):
j = x[p] # i 位になったチーム p は j 位だった
if j > maxi:
resArr.append(p+1)
maxi = j
resArr.sort()
res = '\n'.join(map(str, resArr))
print res
(ΦωΦ)＜おしまい