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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 500010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)
int Hash[N],List[N],rem;
struct SegTree{
int l,r,mid;
bool empty;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r; mid = (l+r)>>1;
empty = true;
}
}t[N<<2];
void PushDown(int rt){
if(!t[rt].empty) return ;
t[lson(rt)].empty = t[rson(rt)].empty = true;
t[rt].empty = false;
}
void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b) return;
int mid = t[rt].mid;
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}
void updata(int rt,int index){
if(t[rt].l == t[rt].r){
t[rt].empty = false; return ;
}
PushDown(rt);
int mid = t[rt].mid;
if(index <= mid) updata(lson(rt),index);
else updata(rson(rt),index);
}
int brute_force(int cnt,int key){
int res = 0;
rem = INF;
for(int i = cnt; i >= 1; i--){
if(List[i]%key < rem){
rem = List[i] % key; res = i;
}
if(rem == 0) return res;
}
return res;
}
int query(int rt,int a,int b){
if(t[rt].empty) return INF;
if(t[rt].l == t[rt].r) return t[rt].l;
PushDown(rt);
int mid = t[rt].mid;
if(b <= mid)
return query(lson(rt),a,b);
else if(a > mid)
return query(rson(rt),a,b);
else{
int res1 = query(lson(rt),a,mid);
if(res1 != INF) return res1;
int res2 = query(rson(rt),mid+1,b);
return min(res1,res2);
}
}
int main(){
build(1,0,N-10);
int cas = 0,Q;
while(scanf("%d",&Q)!=EOF && Q){
if(cas++) puts("");
printf("Case %d:\n",cas);
int cnt = 0; cl(Hash,0); t[1].empty = true;
while(Q--){
char op[5]; int val;
scanf("%s%d",op,&val);
if(op[0] == 'B'){
List[++cnt] = val;
updata(1,val);
Hash[val] = cnt;
}
else{
int ans;
if(cnt == 0){
puts("-1"); continue;
}
if(val <= 1000){
ans = brute_force(cnt,val);
printf("%d\n",ans);
}
else{
int st,en;
st = 0;
en = val-1 <= (N-10) ? val-1 : (N-10);
rem = INF; ans = 0;
while(st <= N-10){
int m = query(1,st,en);
if(m != INF){
if(m%val < rem){
rem = m%val; ans = Hash[m];
}
else if(m%val == rem){
ans = max(ans,Hash[m]);
}
}
st = en+1;
en = (en+val > (N-10) ? (N-10) : en+val);
}
printf("%d\n",ans);
}
}
}
}
return 0;
}
|