Atcoder ARC #022 B. 細長いお菓子

Atcoder ARC #022 B. 細長いお菓子

B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder

数列が与えられるので、その部分列の中で、相異なる数のみを含むもので最長のものの長さを答える問題。すごくシンプルなのだけれど、少し手こずった。いまどの区間の数列を見ているのかを[l, r)として、aiについて場合分けして考える。それぞれの数が出てきたときに、その数がどこに出てきたかをpに記録する。そして、そのaiが今見ている区間からはずれているか、あるいは-1で初期化されたままであれば、区間に追加する。区間に含まれているならば、そのpが示すポインタ＋１の場所をlとしてから区間に追加する。以上を実装すると下のようになる。

#include "bits/stdc++.h"
using namespace std;
#define rep(i, n)             for (int (i) = 0; (i) < (int)(n); (i)++)
template<typename T, typename U> inline void amax(T &x, U y) { if (x < y) x = y; }
int in() { int x; scanf("%d", &x); return x; }

signed main() { 
        int n = in();
        vector<int> p(101010, -1);
        int l = 0, ans = -1;
        rep(r, n) {
                int a = in();
                if (p[a] < l) amax(ans, r - l + 1);
                else l = p[a] + 1;
                p[a] = r;
        }
        cout << ans << endl;
        return 0;
}