AtCoder ABC 378 C - Repeating (5Q, 灰色, 300 点)

map の練習問題！

• 問題へのリンク

問題概要

長さ の数列 が与えられる。

各 について、 かつ を満たす最大の整数 を求めよ（存在しない場合は -1）。

制約

• 
• 

考えたこと

基本的には次の情報を管理できる配列が欲しい。

---

last[v]：その時点で、 を満たす最大の

---

ただし、 という制約を考えると、単純な配列だと ものサイズが必要になってしまう。このようなとき、連想配列が活躍する。連想配列は、配列の添字にさまざまな要素を入れられるようにしたものである。C++ では map 型が使える。

具体的には、map<int,int> 型の変数 last を用意しよう。全体として計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, A;
    cin >> N;

    map<int, int> last;
    for (int i = 0; i < N; i++) {
        cin >> A;
        if (!last.count(A)) cout << -1 << " ";
        else cout << last[A] << " ";
        last[A] = i+1;
    }
    cout << endl;
}