Any hint for solving 1439. Battle with You-Know-Who using Policy Based Data Structure

#1

Link- https://acm.timus.ru/problem.aspx?space=1&num=1439
since making a set of n would give Memory limit error

#2

Hi @yashnahtanaman12345
what u can do is make set of only those number which are destroyed.
like set={}
20 L ->ans=20
5 D-> set ={5}
7 L-> now find how many indexes smaller than 7 have been erased, so here ans=7+1=8
9 D-> now find how many indexes smaller than 7 have been erased, so here set={5,10}
ans so on check for each query.
Hope dis helps.

1 Like
#3

In 9D how is the set formed {5,10}

#4

Link to my code–code
I have done the same except i am not able to figure out what has to be done when second D query comes.

#5

@yashnahtanaman12345
let n=10;
doors={1,2,3,4,5,6,7,8,9,10}
so, L 4 -> ans=4;
D 4 -> set = {4} , doors = {1,2,3,5,6,7,8,9,10}
L 5 - > ans = 6(see from previous step from doors) i.e (5+1=6 )
D 5 -> set = {4,5}(see from 2nd step from doors) i.e (5+1=6 i.e index 5 is added in set) doors={1,2,3,5,7,8,9,10}
D 5 -> set = {4,5,5}see from previous step from doors) i.e (5+2=7 i.e index 5 is added in set). doors = {1,2,3,5,8,9,10}
L 5 -> ans= 8 i.e (5 + upper_bound(5 in set) i.e 5+3=8)
D 6 -> set = {4,5,5,6}, (6+3=9 i.e index 6 is added in set). doors = {1,2,3,5,8,10}
ans so on.
Hope dis helps.
D 5 ->

#6

since n (number of doors<=10^9) we cant keep track of it
could you share the code

#7

and if we just insert all D doors and look for upper bound this tc might fail-

4 4
D 2
D 1
L 1
L 2

Output 2: 3 4