1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
using namespace std;
const int N=1e6+7;
int llen[2][N<<2],rlen[2][N<<2],mlen[2][N<<2],lz[2][N<<2],n,m,T,a,b;
char op[10];
inline void (int o,int len ,int t){
llen[t][o]=llen[t][o<<1];rlen[t][o]=rlen[t][o<<1|1];
if(llen[t][o]==len-(len>>1))llen[t][o]+=llen[t][o<<1|1];
if(rlen[t][o]==len>>1)rlen[t][o]+=rlen[t][o<<1];
mlen[t][o]=max(max(mlen[t][o<<1],mlen[t][o<<1|1]),rlen[t][o<<1]+llen[t][o<<1|1]);
}
inline void pushdown(int o,int len,int t){
if(lz[t][o]==-1)return ;
lz[t][o<<1]=lz[t][o<<1|1]=lz[t][o];
llen[t][o<<1]=rlen[t][o<<1]=mlen[t][o<<1]=lz[t][o]?len-(len>>1):0;
llen[t][o<<1|1]=rlen[t][o<<1|1]=mlen[t][o<<1|1]=lz[t][o]?len>>1:0;
lz[t][o]=-1;
}
inline void build(int o,int l,int r){
rep(t,0,1)llen[t][o]=rlen[t][o]=mlen[t][o]=r-l+1,lz[t][o]=-1;
if(l==r)return ;
int mid=l+r>>1;
build(lson);
build(rson);
}
inline void update(int o,int l,int r,int L,int R,int x,int t){
if(L<=l&&R>=r){
llen[t][o]=rlen[t][o]=mlen[t][o]=x?(r-l+1):0;
lz[t][o]=x;
return ;
}
pushdown(o,r-l+1,t);
int mid=l+r>>1;
if(L<=mid)update(lson,L,R,x,t);
if(R>mid)update(rson,L,R,x,t);
pushup(o,r-l+1,t);
}
inline int query(int o,int l,int r,int L,int R,int x,int t){
if(L==R)return L;
pushdown(o,r-l+1,t);
int mid=l+r>>1;
if(mlen[t][o<<1]>=x)return query(lson,L,mid,x,t);
if(rlen[t][o<<1]+llen[t][o<<1|1]>=x)return mid-rlen[t][o<<1]+1;
return query(rson,mid+1,R,x,t);
}
int main(){
scanf("%d",&T);
rep(k,1,T){
printf("Case %d:n",k);
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--){
scanf("%s",op);
if(op[0]=='D'){
scanf("%d",&a);
if(mlen[0][1]>=a){
printf("%d,let's flyn",b=query(1,1,n,1,n,a,0));
update(1,1,n,b,b+a-1,0,0);
}
else puts("fly with yourself");
}
else if(op[0]=='N'){
scanf("%d",&a);
if(mlen[0][1]>=a){
printf("%d,don't put my gezin",b=query(1,1,n,1,n,a,0));
update(1,1,n,b,b+a-1,0,0);
update(1,1,n,b,b+a-1,0,1);
}
else if(mlen[1][1]>=a){
printf("%d,don't put my gezin",b=query(1,1,n,1,n,a,1));
update(1,1,n,b,b+a-1,0,0);
update(1,1,n,b,b+a-1,0,1);
}
else puts("wait for me");
}
else {
scanf("%d%d",&a,&b);
update(1,1,n,a,b,1,0);
update(1,1,n,a,b,1,1);
puts("I am the hope of chinese chengxuyuan!!");
}
}
}
return 0;
}
|
近期评论