Guest User

Untitled

a guest
May 5th, 2020
117
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifdef DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long double ld;
  10.  
  11. #ifdef DEBUG
  12. #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  13. #else
  14. #define eprintf(...) ;
  15. #endif
  16.  
  17. #define sz(x) ((int) (x).size())
  18. #define TASK "text"
  19.  
  20. const int inf = (int) 1.01e9;
  21. const long long infll = (long long) 1.01e18;
  22. const ld eps = 1e-9;
  23. const ld pi = acos((ld) -1);
  24.  
  25. #ifdef DEBUG
  26. mt19937 mrand(300);
  27. #else
  28. mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
  29. #endif
  30.  
  31. int rnd(int x) {
  32.   return mrand() % x;
  33. }
  34.  
  35. void precalc() {
  36. }
  37.  
  38. const int maxn = (int) 1e6 + 5;
  39. int q;
  40.  
  41. bool read() {
  42.   if (scanf("%d", &q) < 1) {
  43.     return false;
  44.   }
  45.   return true;
  46. }
  47.  
  48. char tmp[2][10];
  49. int a[2 * maxn];
  50. int l, r;
  51. vector<pair<int, pair<int, int>>> p, np;
  52.  
  53. int getX() {
  54.   int x = (int) tmp[1][0];
  55.   if (x == (int) 's') {
  56.     if (tmp[1][1] == 'i') {
  57.       x++;
  58.     }
  59.   }
  60.   return x;
  61. }
  62.  
  63. void solve() {
  64.   l = maxn;
  65.   r = maxn;
  66.   p.clear();
  67.   for (int qq = 0; qq < q; qq++) {
  68.     scanf("%s%s", tmp[0], tmp[1]);
  69.     int x = getX();
  70.     if (!qq) {
  71.       a[r++] = x;
  72.       p.push_back(make_pair(1, make_pair(1, 1)));
  73.     } else {
  74.       np.clear();
  75.       if (tmp[0][0] == 'a') {
  76.         a[r++] = x;
  77.         for (int i = 0; i < sz(p); i++) {
  78.           while (p[i].second.second) {
  79.             int len = p[i].first;
  80.             if (x == a[l + len]) {
  81.               break;
  82.             }
  83.             p[i].first -= p[i].second.first;
  84.             p[i].second.second--;
  85.           }
  86.           if (!p[i].second.second) {
  87.             continue;
  88.           }
  89.           int len = p[i].first;
  90.           len++;
  91.           if (p[i].second.second == 1) {
  92.             np.push_back(make_pair(len, make_pair(1, 1)));
  93.             continue;
  94.           }
  95.           int len1 = p[i].first - p[i].second.first;
  96.           if (x != a[l + len1]) {
  97.             np.push_back(make_pair(len, make_pair(1, 1)));
  98.             continue;
  99.           }
  100.           np.push_back(make_pair(len, p[i].second));
  101.         }
  102.         if (x == a[l]) {
  103.           if (!np.empty() && np.back().first - np.back().second.first * np.back().second.second == 1) {
  104.             np.back().second.second++;
  105.           } else if (!np.empty() && np.back().second.second == 1) {
  106.             np.back().second.first = np.back().first - 1;
  107.             np.back().second.second++;
  108.           } else {
  109.             np.push_back(make_pair(1, make_pair(1, 1)));
  110.           }
  111.         }
  112.       } else {
  113.         a[--l] = x;
  114.         for (int i = 0; i < sz(p); i++) {
  115.           while (p[i].second.second) {
  116.             int len = p[i].first;
  117.             if (x == a[r - len - 1]) {
  118.               break;
  119.             }
  120.             p[i].first -= p[i].second.first;
  121.             p[i].second.second--;
  122.           }
  123.           if (!p[i].second.second) {
  124.             continue;
  125.           }
  126.           int len = p[i].first;
  127.           len++;
  128.           if (p[i].second.second == 1) {
  129.             np.push_back(make_pair(len, make_pair(1, 1)));
  130.             continue;
  131.           }
  132.           int len1 = p[i].first - p[i].second.first;
  133.           if (x != a[r - len1 - 1]) {
  134.             np.push_back(make_pair(len, make_pair(1, 1)));
  135.             continue;
  136.           }
  137.           np.push_back(make_pair(len, p[i].second));
  138.         }
  139.         if (x == a[r - 1]) {
  140.           if (!np.empty() && np.back().first - np.back().second.first * np.back().second.second == 1) {
  141.             np.back().second.second++;
  142.           } else if (!np.empty() && np.back().second.second == 1) {
  143.             np.back().second.first = np.back().first - 1;
  144.             np.back().second.second++;
  145.           } else {
  146.             np.push_back(make_pair(1, make_pair(1, 1)));
  147.           }
  148.         }
  149.       }
  150.       swap(p, np);
  151.     }
  152.     int res = 0;
  153.     for (int i = 0; i < sz(p); i++) {
  154.       res += p[i].second.second;
  155.     }
  156.     printf("%d\n", res);
  157.   }
  158. }
  159.  
  160. int main() {
  161.   precalc();
  162. #ifdef DEBUG
  163.   assert(freopen(TASK ".in", "r", stdin));
  164.   assert(freopen(TASK ".out", "w", stdout));
  165. #endif
  166.   while (read()) {
  167.     solve();
  168. #ifdef DEBUG
  169.     eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
  170. #endif
  171.   }
  172.   return 0;
  173. }
RAW Paste Data