记录编号 |
273660 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOI 2003]文本编辑器 |
最终得分 |
100 |
用户昵称 |
Sky_miner |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.285 s |
提交时间 |
2016-06-23 10:34:05 |
内存使用 |
6.34 MiB |
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define scnaf scanf
#define maxtot 2097252
#define maxsize 5500
#define maxnum 900
int me_po[maxnum],next[maxnum],siz[maxnum];
char data[maxnum][maxsize],res[maxtot];
int n,pos,cnt;
struct list{
int cat_max(const int &a,const int &b){return a>b ? a:b;}
int cat_min(const int &a,const int &b){return a<b ? a:b;}
list(){
for(int i=1;i<maxnum;++i) me_po[i] = i;
cnt = 1;
next[0] = -1;siz[0] = 0;
}
void find(int &p,int &b){
for( b=0 ;b != -1 && p > siz[b] ;b = next[b])
p -= siz[b];
}
int newnode(){return me_po[cnt++];}
void delete_node(int x){me_po[--cnt] = x;}
void copy(int b,int len,char ch[],int ne){
siz[b] = len;next[b] = ne;
memcpy(data[b],ch,len);
}
void split(int p,int b){
if( p == siz[b] || b == -1 ) return ;
int t = newnode();
copy(t,siz[b]-p,data[b] + p,next[b]);
siz[b] = p;next[b] = t;
}
void maintain(int b){
for(;b != -1;b = next[b])
for(int i = next[b] ;i != -1&& siz[b] + siz[i] <= maxsize;i = next[b]){
memcpy(data[b]+siz[b],data[i],siz[i]);
siz[b] += siz[i];next[b] = next[i];
delete_node(i);
}
}
void insert(int now,int len,char res[]){
int b;find(now,b);
split(now,b);
int i,t;
for(i=0;i+maxsize <= len;i+=maxsize){
t = newnode();
copy(t,maxsize,res + i,next[b]);
next[b] = t;b = t;
}
if( len - i ){
t = newnode();
copy(t,len-i,res+i,next[b]);
next[b] = t;
}
maintain(b);
}
void delete_word(int p,int len){
int b,t;
find(p,b);split(p,b);
for(t = next[b];t != -1 && len > siz[t];t = next[t])
len -= siz[t];
split(len,t);t = next[t];
for(int i = next[b];i!=t;i=next[i]){
next[b] = next[i];delete_node(i);
}
maintain(b);
}
void get_data(int p,int len){
int b,i,t;
find(p,b);
i = cat_min(len,siz[b] - p);
memcpy(res,data[b] + p,i);
for(t = next[b]; t != -1 && i + siz[t] <= len;i+=siz[t],t = next[t])
memcpy(res+i,data[t],siz[t]);
if( len - i && t != -1 ) memcpy(res+i,data[t],len-i);
res[len] = '\0';
printf("%s\n",res);
}
};
FILE *___=freopen("editor2003.in","r",stdin);
FILE *_=freopen("editor2003.out","w",stdout);
char ch[100];
int main(){
list cojs;
//printf("point\n");
scnaf("%d",&n);
int x;char c;
for(int i=1;i<=n;++i){
scanf("%s",ch);
if( ch[0] == 'M' ){
scnaf("%d",&pos);
}else if( ch[0] == 'I' ){
scnaf("%d",&x);
for(int i=0;i<x;++i){
while(c = getchar(),c<32 || c> 126);
res[i] = c;
}
cojs.insert(pos,x,res);
}else if(ch[0] == 'D'){
scanf("%d",&x);
cojs.delete_word(pos,x);
}else if(ch[0] == 'G'){
scnaf("%d",&x);
cojs.get_data(pos,x);
}else if(ch[0] == 'P') --pos;
else ++pos;
}
getchar();getchar();
}