Problem:

Set: Range Search

  For a set $S$ of integers, perform a sequence of the following operations. Note that each value in $S$ must be unique.

  
insert($x$): Insert $x$ to $S$ and report the number of elements in $S$ after the operation.

  
find($x$): Report the number of $x$ in $S$ (0 or 1).

  
delete($x$): Delete $x$ from $S$.

  
dump($L$, $R$): Print elements $x$ in $S$ such that $L \leq x \leq R$.

Input

  The input is given in the following format.

$q$
$query_1$
$query_2$
:
$query_q$

Each query $query_i$ is given by

0 $x$

or

1 $x$

or

2 $x$

or

3 $L$ $R$

where the first digits 0, 1, 2 and 3 represent insert, find, delete and dump operations respectively.

Output

For each insert operation, print the number of elements in $S$.

For each find operation, print the number of specified elements in $S$.

For each dump operation, print the corresponding elements in ascending order. Print an element in a line.

Constraints

  
$1 \leq q \leq 200,000$

  
$0 \leq x \leq 1,000,000,000$

The total number of elements printed by dump operations does not exceed $1,000,000$

Sample Input 1

9
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 2 4

Sample Output 1

1
2
3
1
0
1
3
3
4



Sample input:
9
0 1
0 2
0 3
2 2
1 1
1 2
1 3
0 4
3 2 4


Sample output:
1
2
3
1
0
1
3
3
4

Submission status: Wrong Answer

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    while fst < last:
        mid = int((fst+last) / 2)
        if last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if mid == 0:
        l.insert(mid,c)
    elif l[mid] < c:
        mid+=1
        l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1] and S[b] <= a[i][2]:
                print(S[b])

Submission status: Wrong Answer

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    while fst < last:
        mid = int((fst+last) / 2)
        if last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if mid == 0:
        l.insert(mid,c)
    elif l[mid] < c:
        mid+=1
        l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        if not a[i][1] in S:
            binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1] and S[b] <= a[i][2]:
                print(S[b])

Submission status: Wrong Answer

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
    while fst < last:
        mid = int((fst+last) / 2)
        if last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] == c:
        return
    elif l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1] and S[b] <= a[i][2]:
                print(S[b])

Submission status: Wrong Answer

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1]:
                start = b
        for b in range(start,len(S)):
            if S[b] <= a[i][2]:
                print(S[b])
            else:
                break

Submission status: Wrong Answer

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1]:
                start = b
                break
        for b in range(start,len(S)):
            if S[b] <= a[i][2]:
                print(S[b])
            else:
                break

Submission status: Wrong Answer

Solution code:
def binary(l,c,low,index):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        for i in range(len(index)):
            if low[i] > c:
                index[i] += 1
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)
    for i in range(len(index)):
        if low[i] > c:
            index[i] += 1

q = int(input())
S = []
a = []
low = []
for i in range(q):
    a.append(list(map(int,input().split())))
    if a[i][0] == 3:
        low.append(a[i][1])

index = [0]*len(low)

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1],low,index)
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
            for b in range(len(index)):
                if low[b] > a[i][1]:
                    index[b] -= 1
    else:
        for b in range(index[0],len(S)):
            if S[b] <= a[i][2]:
                print(S[b])
            else:
                del low[0]
                del index[0]
                break

Submission status: Wrong Answer

Solution code:
def binary(l,c,low,index):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        for i in range(len(index)):
            if low[i] > c:
                index[i] += 1
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)
    for i in range(len(index)):
        if low[i] > c:
            index[i] += 1

q = int(input())
S = []
a = []
low = []
for i in range(q):
    a.append(list(map(int,input().split())))
    if a[i][0] == 3:
        low.append(a[i][1])

index = [0]*len(low)

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1],low,index)
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
            for b in range(len(index)):
                if low[b] > a[i][1]:
                    index[b] -= 1
    else:
        if index[0] < len(S):
            for b in range(index[0],len(S)):
                if S[b] <= a[i][2]:
                    print(S[b])
                else:
                    del low[0]
                    del index[0]
                    break
        else:
            del low[0]
            del index[0]

Submission status: Wrong Answer

Solution code:
def binary(l,c,low,index):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        for i in range(len(index)):
            if low[i] > c:
                index[i] += 1
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)
    for i in range(len(index)):
        if low[i] > c:
            index[i] += 1

q = int(input())
S = []
a = []
low = []
for i in range(q):
    a.append(list(map(int,input().split())))
    if a[i][0] == 3:
        low.append(a[i][1])

index = [0]*len(low)

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1],low,index)
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
            for b in range(len(index)):
                if low[b] > a[i][1]:
                    index[b] -= 1
    else:
        if index[0] < len(S):
            for b in range(index[0],len(S)):
                if S[b] <= a[i][2]:
                    print(S[b])
                    if b == len(S):
                        del low[0]
                        del index[0]
                else:
                    del low[0]
                    del index[0]
                    break
        else:
            del low[0]
            del index[0]

Submission status: Wrong Answer

Solution code:
# AOJ ITP2_7_C: Set: Range Search
# Python3 2018.6.24 bal4u

from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
cnt = 0
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = int(a[1])
	if a[0] == '0':
		if ki not in dict:
			dict[ki] = 1
			cnt += 1
			insort_left(keytbl, ki)
		print(cnt)
	elif a[0] == '1': print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			cnt -= dict[ki]
			dict[ki] = 0
	else:
		L = bisect_left (keytbl, int(a[1]))
		R = bisect_right(keytbl, int(a[2]), L)
		for j in range(L, R):
			if dict[keytbl[j]] == 1: print(keytbl[j])

Submission status: Wrong Answer

Solution code:

class BinarySearchTree:
    class Node:
        __slots__ = ('key', 'left', 'right', 'count')

        def __init__(self, key):
            self.key = key
            self.left = None
            self.right = None
            self.count = 0

        def __str__(self):
            return "{}, {} ({}, {})".format(self.key, self.count,
                                            self.left, self.right)

    def __init__(self):
        self.root = None

    def put(self, key):
        def _put(node):
            if node is None:
                node = self.Node(key)
            if node.key > key:
                node.left = _put(node.left)
            elif node.key < key:
                node.right = _put(node.right)
            node.count = self._size(node.left) + self._size(node.right) + 1
            return node

        self.root = _put(self.root)

    def __contains__(self, key):
        def _contains(node):
            if node is None:
                return False
            if node.key > key:
                return _contains(node.left)
            elif node.key < key:
                return _contains(node.right)
            else:
                return True
        return _contains(self.root)

    def delete(self, key):
        def _delete(node):
            if node is None:
                return None

            if node.key > key:
                node.left = _delete(node.left)
            elif node.key < key:
                node.right = _delete(node.right)
            else:
                node = _remove(node)

            if node is not None:
                node.count = self._size(node.right) + self._size(node.left) + 1
            return node

        def _remove(node):
            if node.left is None:
                right, node.right = node.right, None
                return right
            elif node.right is None:
                left, node.left = node.left, None
                return left
            else:
                if self._size(node.right) > self._size(node.left):
                    x = _find_min(node.right)
                    x.right = _remove_min(node.right)
                    x.left = node.left
                else:
                    x = _find_max(node.left)
                    x.left = _remove_max(node.left)
                    x.right = node.right
                return x

        def _find_max(node):
            if node.right is None:
                return node
            else:
                return _find_max(node.right)

        def _find_min(node):
            if node.left is None:
                return node
            else:
                return _find_min(node.left)

        def _remove_max(node):
            if node.right is None:
                return node.left
            else:
                node.right = _remove_max(node.right)
                return node

        def _remove_min(node):
            if node.left is None:
                return node.right
            else:
                node.left = _remove_min(node.left)
                return node

        self.root = _delete(self.root)

    @property
    def size(self):
        return self._size(self.root)

    def _size(self, node):
        if node is None:
            return 0
        else:
            return node.count

    def range(self, min_, max_):
        def _range(node):
            if node is None:
                return

            if node.key > max_:
                yield from _range(node.left)
            elif node.key < min_:
                yield from _range(node.right)
            else:
                yield from _range(node.left)
                yield node.key
                yield from _range(node.right)

        if min_ > max_:
            return
        yield from _range(self.root)



class BstSet:
    def __init__(self):
        self.bst = BinarySearchTree()

    def add(self, key):
        self.bst.put(key)

    def __contains__(self, key):
        return key in self.bst

    def delete(self, key):
        self.bst.delete(key)

    def range(self, a, b): 
        for k in self.bst.range(a, b): 
            yield k

    @property
    def count(self):
        return self.bst.size

def run():
    q = int(input())
    s = BstSet()

    for _ in range(q):
        command, *value = [int(x) for x in input().split()]
        if command == 0:
            s.add(value[0])
            print(s.count)
        elif command == 1:
            if value[0] in s:
                print(1)
            else:
                print(0)
        elif command == 2:
            s.delete(value[0])
        elif command == 3:
            for i in s.range(*value):
                print(i)
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:

class BinarySearchTree:
    class Node:
        __slots__ = ('key', 'left', 'right', 'count')

        def __init__(self, key):
            self.key = key
            self.left = None
            self.right = None
            self.count = 0

        def __str__(self):
            return "{}, {} ({}, {})".format(self.key, self.count,
                                            self.left, self.right)

    def __init__(self):
        self.root = None

    def put(self, key):
        def _put(node):
            if node is None:
                node = self.Node(key)
            if node.key > key:
                node.left = _put(node.left)
            elif node.key < key:
                node.right = _put(node.right)
            node.count = self._size(node.left) + self._size(node.right) + 1
            return node

        self.root = _put(self.root)

    def __contains__(self, key):
        def _contains(node):
            if node is None:
                return False
            if node.key > key:
                return _contains(node.left)
            elif node.key < key:
                return _contains(node.right)
            else:
                return True
        return _contains(self.root)

    def delete(self, key):
        def _delete(node):
            if node is None:
                return None

            if node.key > key:
                node.left = _delete(node.left)
            elif node.key < key:
                node.right = _delete(node.right)
            else:
                node = _remove(node)

            if node is not None:
                node.count = self._size(node.right) + self._size(node.left) + 1
            return node

        def _remove(node):
            if node.left is None:
                right, node.right = node.right, None
                return right
            elif node.right is None:
                left, node.left = node.left, None
                return left
            else:
                if self._size(node.right) > self._size(node.left):
                    x = _find_min(node.right)
                    x.right = _remove_min(node.right)
                    x.left = node.left
                else:
                    x = _find_max(node.left)
                    x.left = _remove_max(node.left)
                    x.right = node.right
                return x

        def _find_max(node):
            if node.right is None:
                return node
            else:
                return _find_max(node.right)

        def _find_min(node):
            if node.left is None:
                return node
            else:
                return _find_min(node.left)

        def _remove_max(node):
            if node.right is None:
                return node.left
            else:
                node.right = _remove_max(node.right)
                node.count = self._size(node.right) + self._size(node.left) + 1
                return node

        def _remove_min(node):
            if node.left is None:
                return node.right
            else:
                node.left = _remove_min(node.left)
                node.count = self._size(node.right) + self._size(node.left) + 1
                return node

        self.root = _delete(self.root)

    @property
    def size(self):
        return self._size(self.root)

    def _size(self, node):
        if node is None:
            return 0
        else:
            return node.count

    def range(self, min_, max_):
        def _range(node):
            if node is None:
                return

            if node.key > max_:
                yield from _range(node.left)
            elif node.key < min_:
                yield from _range(node.right)
            else:
                yield from _range(node.left)
                yield node.key
                yield from _range(node.right)

        if min_ > max_:
            return
        yield from _range(self.root)

class BstSet:
    def __init__(self):
        self.bst = BinarySearchTree()

    def add(self, key):
        self.bst.put(key)

    def __contains__(self, key):
        return key in self.bst

    def delete(self, key):
        self.bst.delete(key)

    def range(self, a, b):
        for k in self.bst.range(a, b):
            yield k

    @property
    def count(self):
        return self.bst.size

    def __str__(self):
        return str(self.bst.root)

def run():
    q = int(input())
    s = BstSet()

    for _ in range(q):
        command, *value = [int(x) for x in input().split()]
        print('>>', command, value)
        if command == 0:
            s.add(value[0])
            print(s.count)
        elif command == 1:
            if value[0] in s:
                print(1)
            else:
                print(0)
        elif command == 2:
            s.delete(value[0])
        elif command == 3:
            for i in s.range(*value):
                print(i)
        else:
            raise ValueError('invalid command')
        print(s)


if __name__ == '__main__':
    run()

Submission status: Time Limit Exceeded

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    while fst < last:
        mid = int((fst+last) / 2)
        if last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        if not a[i][1] in S:
            if not S:
                S.append(a[i][1])
            else:
                binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1] and S[b] <= a[i][2]:
                print(S[b])

Submission status: Time Limit Exceeded

Solution code:
def binary(l,c):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)

q = int(input())
S = []
a = []
for i in range(q):
    a.append(list(map(int,input().split())))

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1])
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
    else:
        for b in range(len(S)):
            if S[b] >= a[i][1]:
                for c in range(b,len(S)):
                    if S[c] <= a[i][2]:
                        print(S[c])
                    else:
                        break
                break

Submission status: Time Limit Exceeded

Solution code:
def binary(l,c,low,index):
    fst = 0
    last = len(l)
    mid = int(last/2)
    if fst == 0 and last ==0:
        l.insert(0,c)
        for i in range(len(index)):
            if low[i] > c:
                index[i] += 1
        return
    while fst < last:
        mid = int((fst+last) / 2)
        if l[mid] == c:
            return
        elif last == mid:
            break
        elif fst == mid:
            break
        elif l[mid] >= c:
            last = mid
        elif l[mid] <= c:
            fst = mid
    if l[mid] < c:
        mid+=1
    l.insert(mid,c)
    for i in range(len(index)):
        if low[i] > c:
            index[i] += 1

q = int(input())
S = []
a = []
low = []
for i in range(q):
    a.append(list(map(int,input().split())))
    if a[i][0] == 3:
        low.append(a[i][1])

index = [0]*len(low)

for i in range(q):
    if a[i][0] == 0:
        binary(S,a[i][1],low,index)
        print(len(S))
    elif a[i][0] == 1:
        if a[i][1] in S:
            print(1)
        else:
            print(0)
    elif a[i][0] == 2:
        if a[i][1] in S:
            S.remove(a[i][1])
            for b in range(len(index)):
                if low[b] > a[i][1]:
                    index[b] -= 1
    else:
        if index[0] < len(S):
            for b in range(index[0],len(S)):
                if S[b] <= a[i][2]:
                    print(S[b])
                    if b == len(S)-1:
                        del low[0]
                        del index[0]
                else:
                    del low[0]
                    del index[0]
                    break
        else:
            del low[0]
            del index[0]

Submission status: Memory Limit Exceeded

Solution code:
numset = set([])
q = int(input())
for i in range(q):
    q, *val = list(map(int, input().split(' ')))
    if q == 0:
        numset.add(val[0])
        print(len(numset))
    elif q == 1:
        rst = 1 if set(val).issubset(numset) else 0
        print(rst)
    elif q == 2:
        if val[0] in numset: numset.remove(val[0])
    elif q == 3:
        nums = [x for x in range(val[0], val[1]+1)]
        for num in nums:
            if num in numset: print(num)

Submission status: Accepted

Solution code:
# AOJ ITP2_7_C: Set: Range Search
# Python3 2018.6.24 bal4u

from bisect import bisect_left, bisect_right, insort_left
dict = {}
keytbl = []
cnt = 0
q = int(input())
for i in range(q):
	a = list(input().split())
	ki = int(a[1])
	if a[0] == '0':
		if ki not in dict:
			dict[ki] = 1
			cnt += 1
			insort_left(keytbl, ki)
		elif dict[ki] == 0:
			dict[ki] = 1
			cnt += 1
		print(cnt)
	elif a[0] == '1': print(dict[ki] if ki in dict else 0)
	elif a[0] == '2':
		if ki in dict:
			cnt -= dict[ki]
			dict[ki] = 0
	else:
		L = bisect_left (keytbl, int(a[1]))
		R = bisect_right(keytbl, int(a[2]), L)
		for j in range(L, R):
			if dict[keytbl[j]] == 1: print(keytbl[j])