#include <bits/stdc++.h>
#define vec vector
#define forn(i, s, f) for (int i = s; i <= f; ++i)
#define pb push_back
#define sz(x) (int)((int)(x).size())
#define endl '\n'
using namespace std;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
typedef pair <int, int> pii;
const int N = 1e6 + 10;
const int buben = 1020;
int id[N];
deque <char> st[buben];
inline void solve () {
int n, q; cin >> n >> q;
string s; cin >> s;
for (int i = 0; i < n; ++i) st[i / buben].pb(s[i]);
int nb = (n + buben - 1) / buben;
int iter = 0;
while (q--) {
char t; cin >> t;
if (t == 'a') {
int i, j; cin >> i >> j; --i, --j;
int uk = 0;
char c = 'a';
while (uk < nb) {
if (i < sz(st[uk])) {
c = st[uk][i];
st[uk].erase(st[uk].begin() + i);
break;
}
i -= sz(st[uk++]);
}
bool ins = 0;
uk = 0;
while (uk < nb) {
if (j < sz(st[uk])) {
st[uk].insert(st[uk].begin() + j, c);
ins = 1;
break;
}
j -= sz(st[uk++]);
}
if (!ins) st[uk].insert(st[uk].begin() + j, c), ++nb;
}
else {
int i; cin >> i; --i;
int uk = 0;
while (uk < nb) {
if (i < sz(st[uk])) {
cout << st[uk][i] << endl;
break;
}
i -= sz(st[uk++]);
}
}
if (iter % buben == 0) {
for (int i = 0; i + 1 < nb; ++i) {
while (sz(st[i]) < buben) {
st[i].pb(st[i + 1][0]);
st[i + 1].pop_front();
}
while (sz(st[i]) > buben) {
st[i + 1].push_front(st[i].back());
st[i].pop_back();
}
}
while (!sz(st[nb - 1])) --nb;
}
++iter;
}
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
// freopen("collider.in", "r", stdin);
// freopen("collider.out", "w", stdout);
#endif
int t = 1; // cin >> t;
while (t--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
980 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
1884 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
