#include <stdio.h>
#define N 1000000
#define Q 15000
#define N_ (N + Q + 1)
unsigned int Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int zz[N_], ll[N_], rr[N_], kk[N_], u_, l_, r_; char cc_[N_];
int node(char c) {
static int _ = 1;
zz[_] = rand_();
kk[_] = 1;
cc_[_] = c;
return _++;
}
void pul(int u) {
kk[u] = kk[ll[u]] + kk[rr[u]] + 1;
}
void split(int u, int k) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
if (kk[ll[u]] < k) {
split(rr[u], k - kk[ll[u]] - 1);
rr[u] = l_, l_ = u;
} else {
split(ll[u], k);
ll[u] = r_, r_ = u;
}
pul(u);
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v), pul(u);
return u;
} else {
ll[v] = merge(u, ll[v]), pul(v);
return v;
}
}
int first(int u) {
return ll[u] == 0 ? u : first(ll[u]);
}
int remove_first(int u) {
if (ll[u] == 0)
return rr[u];
ll[u] = remove_first(ll[u]), pul(u);
return u;
}
int main() {
static char cc[N + 1];
int n, m, i, j;
scanf("%d%d%s", &n, &m, cc);
for (i = 0; i < n; i++)
u_ = merge(u_, node(cc[i]));
while (m--) {
static char s[2];
char c;
scanf("%s", s);
if (s[0] == 'a') {
scanf("%d%d", &i, &j), i--, j--;
split(u_, i);
c = cc_[first(r_)];
u_ = merge(l_, remove_first(r_));
split(u_, j);
u_ = merge(merge(l_, node(c)), r_);
} else {
scanf("%d", &i), i--;
split(u_, i);
printf("%c\n", cc_[first(r_)]);
u_ = merge(l_, r_);
}
}
return 0;
}
Compilation message
collider.c: In function 'main':
collider.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d%s", &n, &m, cc);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
collider.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%s", s);
| ^~~~~~~~~~~~~~
collider.c:81:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
collider.c:88:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d", &i), i--;
| ^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
9 ms |
568 KB |
Output is correct |
| 3 |
Correct |
23 ms |
2288 KB |
Output is correct |
| 4 |
Correct |
116 ms |
15200 KB |
Output is correct |
| 5 |
Correct |
126 ms |
15436 KB |
Output is correct |
| 6 |
Correct |
153 ms |
17416 KB |
Output is correct |
| 7 |
Correct |
192 ms |
19260 KB |
Output is correct |
| 8 |
Correct |
134 ms |
19028 KB |
Output is correct |
| 9 |
Correct |
181 ms |
19260 KB |
Output is correct |
| 10 |
Correct |
155 ms |
19132 KB |
Output is correct |
