Advertisement
erek1e

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

Jun 23rd, 2022
967
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e6 + 1, L = 20 + 1;
  6. int removeLast[L][N], len[N]; // binary lifting
  7. /* removeLast[i][j] = how many operations behind operation j had
  8. the same string but with the last 2^i characters removed */
  9. char lastLetter[N];
  10.  
  11. int goBack(int from, int steps) {
  12.     for (int i = 0; i < L && from > 0; ++i) {
  13.         if ((1 << i) & steps) from = from - removeLast[i][from];
  14.     }
  15.     if (from < 0) from = 0;
  16.     return from;
  17. }
  18.  
  19. int main() {
  20.     int q; cin >> q;
  21.     int n = 0; // number of operations that are not questions
  22.     for (int k = 1; k <= q; ++k) {
  23.         char type; cin >> type;
  24.         if (type == 'P') {
  25.             int p; cin >> p;
  26.             cout << lastLetter[goBack(n, len[n]-1-p)] << endl;
  27.         } else {
  28.             ++n;
  29.             if (type == 'T') {
  30.                 char c; cin >> c;
  31.                 lastLetter[n] = c;
  32.                 len[n] = len[n-1]+1;
  33.                 removeLast[0][n] = 1;
  34.             } else { // type == 'U'
  35.                 int u; cin >> u;
  36.                 ++u;
  37.                 lastLetter[n] = lastLetter[n-u];
  38.                 len[n] = len[n-u];
  39.                 removeLast[0][n] = u+removeLast[0][n-u];
  40.             }
  41.             // perform binary lifting for q
  42.             for (int i = 1; i < L; ++i) removeLast[i][n] = removeLast[i-1][n] + removeLast[i-1][n-removeLast[i-1][n]];
  43.         }
  44.     }
  45.     return 0;
  46. }
Advertisement
RAW Paste Data Copied
Advertisement