yukicoder No.318 学学学学学
解法
解法はこの問題に似ている気がします。
mayokoex.hatenablog.com
大きい数が最後に挟み撃ちするということは, 要するに大きい数のほうが優先的に採用されるということなので, 大きい数から順番に数を決定していきます。
このように考えると, i 番目の要素の数が決定した場合はもう i 番目の要素については調べる必要がないです。調べるひつようのある index を set で管理しておき, その index における数が決定したら set からその index を削除する, ということを行えば要素を調べる回数は n 回で済み, 時間内に答えを得ることが出来ます。
const int MAXN = 100010; int ans[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; map<int, pii> M; for (int i = 0; i < n; i++) { int a; cin >> a; if (M.find(a) == M.end()) { M[a].first = i; M[a].second = i; } else { M[a].first = min(M[a].first, i); M[a].second = max(M[a].first, i); } } set<int> S; for (int i = 0; i < n; i++) S.insert(i); for (auto it = M.rbegin(); it != M.rend(); it++) { pii p = (*it).second; for (auto ite = S.lower_bound(p.first); ite != S.end() && (*ite) <= p.second; ) { ans[(*ite)] = (*it).first; ite = S.erase(ite); } } for (int i = 0; i < n; i++) { cout << ans[i]; if (i < n-1) cout << " "; } cout << endl; return 0; }