Guest User

Untitled

a guest
Aug 9th, 2015
167
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <assert.h>
  3. #include <unordered_map>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef vector < long long > vll;
  9. typedef pair < long long, long long > pll;
  10. typedef pair < int, int > pii;
  11. typedef vector < int > vii;
  12.  
  13. #define csl ios_base::sync_with_stdio(false); cin.tie(NULL)
  14. #define l(x) (((x) << 1) | 1)
  15. #define r(x) ((l(x)) + 1)
  16. #define mp make_pair
  17. #define fst first
  18. #define snd second
  19.  
  20. ll t, n, u, v, m, q, r, ql, qr, k, l, s, x, y, w;
  21. const int N = 1e6 + 500;
  22. const int LN = 23;
  23. const long long mod = 1e9 + 7;
  24. const long long INF = 1LL << 57LL;
  25. const bool JUDGE = false;
  26. int h = 1;
  27. struct node{
  28.     char letter;
  29.     int time;
  30.     int parent;
  31.     int L[LN];
  32.     node () {
  33.         parent = -1;
  34.         time = 0;
  35.         letter = '$';
  36.         memset(L, -1, sizeof(L));
  37.     }
  38.     node (char letter, int time, int parent) {
  39.         this -> letter = letter;
  40.         this -> time = time;
  41.         this -> parent = parent;
  42.         memset(L, -1, sizeof(L));
  43.     }
  44. }trie[N];
  45. inline void typeletter(char l) {
  46.     trie[h].letter = l;
  47.     trie[h].time = trie[h - 1].time + 1;
  48.     trie[h].parent = h - 1;
  49.     trie[h].L[0] = trie[h].parent;
  50.     for (int i = 0; i < LN - 1; ++i) {
  51.         if (trie[h].L[i] == -1) break;
  52.         trie[h].L[i + 1] = trie[trie[h].L[i]].L[i];
  53.     }
  54.     h++;
  55. }
  56. inline void undo(int x) {
  57.     trie[h] = trie[h - x - 1];
  58.     h++;
  59. }
  60. char getletter(int x) {
  61.     int j = trie[h - 1].time;
  62.     j = j - x;
  63.     x = h - 1;
  64.     for (int i = 0; i < LN; ++i) {
  65.         if (j & (1 << i)) {
  66.             //cout << x << " " ;
  67.             x = trie[x].L[i];
  68.             //cout << x << '\n';
  69.         }
  70.     }
  71.     return trie[x].letter;
  72. }
  73. char str;
  74. int main(){
  75.     csl;
  76.     if (JUDGE) {
  77.         freopen("in.txt", "r", stdin);
  78.         freopen("out.txt", "w", stdout);
  79.     }
  80.     cin >> n;
  81.     for (int i = 0; i < n; ++i) {
  82.         cin >> str;
  83.         if (str == 'T') {
  84.             char x;
  85.             cin >> x;
  86.             typeletter(x);
  87.         }
  88.         else if (str == 'P') {
  89.             cin >> u;
  90.             cout << getletter(int(u) + 1) << '\n';
  91.         }
  92.         else {
  93.             cin >> u;
  94.             undo(u);
  95.         }
  96.     /*  for (int i = 1; i < h; ++i) {
  97.             cout << trie[i].letter << " " << trie[i].time << " " << trie[i].parent << '\n';
  98.         }*/
  99.     }
  100.     return 0;
  101. }
RAW Paste Data