SHOW:
|
|
- or go back to the newest paste.
| 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 | } |
