Official
B - Which is ahead? Editorial by nok0
人 \(i\) は前から \(Q_i\) 番目に並んでいるという情報を表す配列 \(Q\) を作成します。
すると、クエリは \(Q_{A_i}\) と \(Q_{B_i}\) の大小の比較となり、簡単に行うことが出来ます。
\(Q\) の作成方法ですが、各 \(i\) について \(Q_{P_i}=i\) とすればよいです。
以下に、C++ 言語による正解例を記載します。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> P(n);
for(int i = 0; i < n; i++) cin >> P[i];
vector<int> Q(n + 1);
for(int i = 0; i < n; i++) Q[P[i]] = i;
int q;
cin >> q;
for(int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
if(Q[a] < Q[b])
cout << a << endl;
else
cout << b << endl;
}
}
posted:
last update: