6051번: Time Travel

https://www.acmicpc.net/problem/6051


$O(n)$

최근 ID 와 바로 이전 ID 가 최근인 시각을 저장한다.

#include<cstdio>
int n, fr[80001], k, r[80001] = { -1 };
char q;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf(" %c", &q);
        if (q == 's') fr[i] = fr[fr[i - 1]], r[i] = r[fr[i - 1]];
        else {
            scanf("%d", &k);
            if (q == 'a') fr[i] = i - 1, r[i] = k;
            else fr[i] = fr[k - 1], r[i] = r[k - 1];
        }
        printf("%d\n", r[i]);
    }
    return 0;
}