#include<stdio.h>
#include<math.h>
#include<string.h>
int x,y,w,n,k,m,top[3010];
char arr[1000010],dap,t,a[1000010],c,bucket[3010][3010];
void update(int x,int y)
{
int i,j,cnt=0,r;
for(i=1;i<=w;i++){
if(top[i]+cnt>=x){
for(j=1;j<=k*2;j++){
if(bucket[i][j]!=0) cnt++;
if(cnt==x){t=bucket[i][j]; bucket[i][j]=0, top[i]--;break;}
}
break;
}
cnt+=top[i];
}
cnt=0;
for(i=1;i<=w;i++){
if(top[i]+cnt>=y){
for(j=1;j<=k*2;j++){
if(bucket[i][j]!=0) cnt++;
if(cnt==y) break;
}
for(r=k*2;r>=j+1;r--) bucket[i][r]=bucket[i][r-1];
bucket[i][j]=t; top[i]++;
break;
}
cnt+=top[i];
}
}
char query(int x)
{
int i,j,cnt=0;
for(i=1;i<=w;i++){
if(top[i]+cnt>=x){
for(j=1;j<=k*2;j++){
if(bucket[i][j]!=0) cnt++;
if(cnt==x) return bucket[i][j];
}
break;
}
cnt+=top[i];
}
}
void clearing()
{
int i,j,cnt=0;
for(i=1;i<=w;i++){
for(j=1;j<=k*2;j++){
if(bucket[i][j]!=0) arr[++cnt]=bucket[i][j];
}
}
w=0;
memset(top,0,sizeof top);
memset(bucket,0,sizeof bucket);
for(i=1;i<=n;i++){
if(i%k==1) w++;
bucket[w][++top[w]]=arr[i];
}
}
int main()
{
int i;
scanf("%d %d",&n,&m);
scanf("%s",a);
for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
k=sqrt(n);
for(i=1;i<=n;i++)
{
if(i%k==1) w++;
bucket[w][++top[w]]=a[i];
}
for(i=1;i<=m;i++)
{
scanf(" %c",&c);
if(c=='a'){
scanf("%d %d",&x,&y);
update(x,y);
}
else{
scanf("%d",&x);
dap=query(x);
printf("%c\n",dap);
}
if(i%k==0) clearing();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
11924 KB |
Output is correct |
| 2 |
Incorrect |
197 ms |
11924 KB |
Output isn't correct |
| 3 |
Correct |
34 ms |
11924 KB |
Output is correct |
| 4 |
Correct |
61 ms |
11924 KB |
Output is correct |
| 5 |
Correct |
130 ms |
11924 KB |
Output is correct |
| 6 |
Correct |
159 ms |
11924 KB |
Output is correct |
| 7 |
Correct |
163 ms |
11924 KB |
Output is correct |
| 8 |
Correct |
73 ms |
11924 KB |
Output is correct |
| 9 |
Correct |
214 ms |
11924 KB |
Output is correct |
| 10 |
Correct |
141 ms |
11924 KB |
Output is correct |
