IOI '12 P3 - Crayfish Scrivener (Standard I/O)

#include <iostream>

using namespace std;

const int N = 1e6 + 1, L = 20 + 1;
int removeLast[L][N], len[N]; // binary lifting
/* removeLast[i][j] = how many operations behind operation j had
the same string but with the last 2^i characters removed */
char lastLetter[N];

int goBack(int from, int steps) {
    for (int i = 0; i < L && from > 0; ++i) {
        if ((1 << i) & steps) from = from - removeLast[i][from];
    }
    if (from < 0) from = 0;
    return from;
}

int main() {
    int q; cin >> q;
    int n = 0; // number of operations that are not questions
    for (int k = 1; k <= q; ++k) {
        char type; cin >> type;
        if (type == 'P') {
            int p; cin >> p;
            cout << lastLetter[goBack(n, len[n]-1-p)] << endl;
        } else {
            ++n;
            if (type == 'T') {
                char c; cin >> c;
                lastLetter[n] = c;
                len[n] = len[n-1]+1;
                removeLast[0][n] = 1;
            } else { // type == 'U'
                int u; cin >> u;
                ++u;
                lastLetter[n] = lastLetter[n-u];
                len[n] = len[n-u];
                removeLast[0][n] = u+removeLast[0][n-u];
            }
            // perform binary lifting for q
            for (int i = 1; i < L; ++i) removeLast[i][n] = removeLast[i-1][n] + removeLast[i-1][n-removeLast[i-1][n]];
        }
    }
    return 0;
}