Problem:

Map: Range Search

  For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

  
insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$.

  
get($key$): Print the value with the specified $key$. Print 0 if there is no such element. 

  
delete($key$): Delete the element with the specified $key$.

  
dump($L$, $R$): Print all elements formed by a pair of the key and the value such that the key is greater than or equal to $L$ and less than or equal to $R$ in lexicographic order.

Input

  The input is given in the following format.

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

Each query $query_i$ is given by

0 $key$ $x$

or

1 $key$

or

2 $key$

or

3 $L$ $R$

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

Output

For each get operation, print the corresponding value.

For each dump operation, print the corresponding elements formed by a pair of the key and the value. For the dump operation, print the elements (a pair of key and value separated by a space character) in ascending order of the keys.

Constraints

  
$1 \leq q \leq 200,000$

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

  
$1 \leq $ length of $key$ $ \leq 20$ 

  
$key$ consists of lower-case letters

  
$L \leq R$ in lexicographic order

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

Sample Input 1

9
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red
3 w z

Sample Output 1

1
4
0
0
white 5



Sample input:
9
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red
3 w z


Sample output:
1
4
0
0
white 5

Submission status: Wrong Answer

Solution code:

from collections import OrderedDict

dict = OrderedDict()
q = int(input())
for i in range(q):
    query, *val = input().split(' ')
    if query == '0':
        dict[val[0]] = int(val[1])
    elif query == '1':
        print(dict.get(val[0], 0))
    elif query == '2':
        if val[0] in dict:
            dict.pop(val[0])
    else:
        ans = ''
        for k, v in dict.items():
            if val[0] <= k and k <= val[1]:
                ans += str(k) + ' ' + str(v) + ' '
        print(ans.strip())

Submission status: Accepted

Solution code:
from enum import Enum
 
 
class Color(Enum):
    BLACK = 0
    RED = 1
 
    @staticmethod
    def flip(c):
        return [Color.RED, Color.BLACK][c.value]
 
 
class Node:
    __slots__ = ('key', 'left', 'right', 'size', 'color', 'value')
 
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = Leaf
        self.right = Leaf
        self.size = 1
        self.color = Color.RED
 
    def is_red(self):
        return self.color == Color.RED
 
    def is_black(self):
        return self.color == Color.BLACK
 
    def __str__(self):
        if self.color == Color.RED:
            key = '*{}'.format(self.key)
        else:
            key = '{}'.format(self.key)
        return "{}[{}] ({}, {})".format(key, self.size,
                                        self.left, self.right)
 
 
class LeafNode(Node):
    def __init__(self):
        self.key = None
        self.value = None
        self.left = None
        self.right = None
        self.size = 0
        self.color = None
 
    def is_red(self):
        return False
 
    def is_black(self):
        return False
 
    def __str__(self):
        return '-'
 
 
Leaf = LeafNode()
 
 
class RedBlackBinarySearchTree:
    """Red Black Binary Search Tree with range, min, max.
    Originally impremented in the textbook
    Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne,
    Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
    """
 
    def __init__(self):
        self.root = Leaf
 
    def put(self, key, value=None):
        def _put(node):
            if node is Leaf:
                node = Node(key, value)
            if node.key > key:
                node.left = _put(node.left)
            elif node.key < key:
                node.right = _put(node.right)
            else:
                node.value = value
 
            node = self._restore(node)
 
            node.size = node.left.size + node.right.size + 1
            return node
 
        self.root = _put(self.root)
        self.root.color = Color.BLACK
 
    def _rotate_left(self, node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = Color.RED
        node.size = node.left.size + node.right.size + 1
        return x
 
    def _rotate_right(self, node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = Color.RED
        node.size = node.left.size + node.right.size + 1
        return x
 
    def _flip_colors(self, node):
        node.color = Color.flip(node.color)
        node.left.color = Color.flip(node.left.color)
        node.right.color = Color.flip(node.right.color)
        return node
 
    def __contains__(self, key):
        def _contains(node):
            if node is Leaf:
                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 get(self, key):
        def _get(node):
            if node is Leaf:
                return None
            if node.key > key:
                return _get(node.left)
            elif node.key < key:
                return _get(node.right)
            else:
                return node.value
        return _get(self.root)
 
    def delete(self, key):
        def _delete(node):
            if node is Leaf:
                return Leaf
 
            if node.key > key:
                if node.left is Leaf:
                    return self._balance(node)
                if not self._is_red_left(node):
                    node = self._red_left(node)
                node.left = _delete(node.left)
            else:
                if node.left.is_red():
                    node = self._rotate_right(node)
                if node.key == key and node.right is Leaf:
                    return Leaf
                elif node.right is Leaf:
                    return self._balance(node)
                if not self._is_red_right(node):
                    node = self._red_right(node)
                if node.key == key:
                    x = self._find_min(node.right)
                    node.key = x.key
                    node.value = x.value
                    node.right = self._delete_min(node.right)
                else:
                    node.right = _delete(node.right)
 
            return self._balance(node)
 
        if self.is_empty():
            raise ValueError('delete on empty tree')
        if not self.root.left.is_red() and not self.root.right.is_red():
            self.root.color = Color.RED
        self.root = _delete(self.root)
        if not self.is_empty():
            self.root.color = Color.BLACK
 
    def delete_max(self):
        if self.is_empty():
            raise ValueError('delete max on empty tree')
        if not self.root.left.is_red() and not self.root.right.is_red():
            self.root.color = Color.RED
        self.root = self._delete_max(self.root)
        if not self.is_empty():
            self.root.color = Color.BLACK
 
    def _delete_max(self, node):
        if node.left.is_red():
            node = self._rotate_right(node)
        if node.right is Leaf:
            return Leaf
 
        if not self._is_red_right(node):
            node = self._red_right(node)
        node.right = self._delete_max(node.right)
        return self._balance(node)
 
    def _red_right(self, node):
        node = self._flip_colors(node)
        if node.left.left.is_red():
            node = self._rotate_right(node)
        return node
 
    def _is_red_right(self, node):
        return (node.right.is_red() or
                (node.right.is_black() and node.right.left.is_red()))
 
    def delete_min(self):
        if self.is_empty():
            raise ValueError('delete min on empty tree')
 
        if not self.root.left.is_red() and not self.root.right.is_red():
            self.root.color = Color.RED
        self.root = self._delete_min(self.root)
        if not self.is_empty():
            self.root.color = Color.BLACK
 
    def _delete_min(self, node):
        if node.left is Leaf:
            return Leaf
 
        if not self._is_red_left(node):
            node = self._red_left(node)
        node.left = self._delete_min(node.left)
        return self._balance(node)
 
    def _red_left(self, node):
        node = self._flip_colors(node)
        if node.right.left.is_red():
            node.right = self._rotate_right(node.right)
            node = self._rotate_left(node)
        return node
 
    def _is_red_left(self, node):
        return (node.left.is_red() or
                (node.left.is_black() and node.left.left.is_red()))
 
    def _balance(self, node):
        if node.right.is_red():
            node = self._rotate_left(node)
        return self._restore(node)
 
    def _restore(self, node):
        if node.right.is_red() and not node.left.is_red():
            node = self._rotate_left(node)
        if node.left.is_red() and node.left.left.is_red():
            node = self._rotate_right(node)
        if node.left.is_red() and node.right.is_red():
            node = self._flip_colors(node)
 
        node.size = node.left.size + node.right.size + 1
        return node
 
    def is_empty(self):
        return self.root is Leaf
 
    def is_balanced(self):
        if self.is_empty():
            return True
 
        try:
            left = self._depth(self.root.left)
            right = self._depth(self.root.right)
            return left == right
        except Exception:
            return False
 
    @property
    def depth(self):
        return self._depth(self.root)
 
    def _depth(self, node):
        if node is Leaf:
            return 0
        if node.right.is_red():
            raise Exception('right red')
        left = self._depth(node.left)
        right = self._depth(node.right)
        if left != right:
            raise Exception('unbalanced')
        if node.is_red():
            return left
        else:
            return 1 + left
 
    def __len__(self):
        return self.root.size
 
    @property
    def max(self):
        if self.is_empty():
            raise ValueError('max on empty tree')
        return self._max(self.root)
 
    def _max(self, node):
        x = self._find_max(node)
        return x.key
 
    def _find_max(self, node):
        if node.right is Leaf:
            return node
        else:
            return self._find_max(node.right)
 
    @property
    def min(self):
        if self.is_empty():
            raise ValueError('min on empty tree')
        return self._min(self.root)
 
    def _min(self, node):
        x = self._find_min(node)
        return x.key
 
    def _find_min(self, node):
        if node.left is Leaf:
            return node
        else:
            return self._find_min(node.left)
 
    def __iter__(self):
        def inorder(node):
            if node is Leaf:
                return
            yield from inorder(node.left)
            yield node.value
            yield from inorder(node.right)
        yield from inorder(self.root)
 
    def range(self, min_, max_):
        def _range(node):
            if node is Leaf:
                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, node.value)
                yield from _range(node.right)
 
        if min_ > max_:
            return
        yield from _range(self.root)
 
 
class Map:
 
    def __init__(self):
        self.tree = RedBlackBinarySearchTree()
 
    def __getitem__(self, key):
        if key in self.tree:
            return self.tree.get(key)
        else:
            raise IndexError('key {} not found in map'.format(key))
 
    def __setitem__(self, key, value):
        self.tree.put(key, value)
 
    def __delitem__(self, key):
        if key in self.tree:
            self.tree.delete(key)
        else:
            raise IndexError('key {} not found in map'.format(key))
 
    def __len__(self):
        return len(self.tree)
 
    def items(self):
        for k, v in self.tree:
            yield (k, v)
 
    def range(self, min_, max_):
        for k, v in self.tree.range(min_, max_):
            yield (k, v)
 
 
def run():
    q = int(input())
    m = Map()
 
    for _ in range(q):
        command, *args = input().split()
        if command == '0':
            key = args[0]
            value = int(args[1])
            m[key] = value
        elif command == '1':
            key = args[0]
            try:
                print(m[key])
            except IndexError:
                print(0)
        elif command == '2':
            key = args[0]
            try:
                del m[key]
            except IndexError:
                pass
        elif command == '3':
            low, hi = args
            for k, v in m.range(low, hi):
                print(k, v)
        else:
            raise ValueError('invalid command')
 
 
if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# AOJ ITP2_8_C: Map: Range Search
# Python3 2018.6.24 bal4u

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

Submission status: Accepted

Solution code:
def resolve():
    import sys
    import bisect
    input = sys.stdin.readline
    n = int(input())
    ans = dict()
    need_sort = True
    sorted_keys = None
    for _ in range(n):
        q, key, *x = input().split()
        if q == "0":
            if key in ans:
                ans[key] = x[0]
            else:
                ans[key] = x[0]
                need_sort = True
        elif q == "1":
            if key in ans:
                print(ans[key])
            else:
                print(0)
        elif q == "2":
            ans[key] = "0"
        else:
            if sorted_keys is None:
                sorted_keys = sorted(ans.keys())
            if need_sort:
                sorted_keys = sorted(ans.keys())
                need_sort = False
            l, r = key, x[0]
            fr = bisect.bisect_left(sorted_keys, l)
            to = bisect.bisect_right(sorted_keys, r)
            for i in range(fr, to):
                if ans[sorted_keys[i]] != "0":
                    print(sorted_keys[i], ans[sorted_keys[i]])


resolve()

Submission status: Accepted

Solution code:
from bisect import bisect,bisect_left,insort
dic = {}
l = []
for i in range(int(input())):
    order = list(input().split())

    if order[0] == "0":
        if order[1] in dic:
            dic[order[1]] = int(order[2])
        else:
            dic[order[1]] = int(order[2])
            insort(l,order[1])
    elif order[0] == "1":
        if order[1] in dic:
            print(dic[order[1]])
        else:
            print(0)
    elif order[0] == "2":
        if order[1] in dic:
            dic[order[1]] = 0
    elif order[0] == "3":
        L = bisect_left(l,order[1])
        R = bisect(l,order[2])
        for i in range(L,R):
            if dic[l[i]]:
                print(l[i],dic[l[i]])

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

def main():
    q = int(input())
    d = defaultdict(int)

    inserted_flag = False
    sorted_keys = None

    for _ in range(q):
        para = input().split()

        if para[0] == "0":
            d[para[1]] = int(para[2])
            inserted_flag = True

        elif para[0] == "1":
            if para[1] in d.keys():
                print(d[para[1]])
            else:
                print("0")

        elif para[0] == "2":
            if para[1] in d.keys():
                del d[para[1]]
                inserted_flag = True
            
        elif para[0] == "3":
            if sorted_keys is None:
                sorted_keys = sorted(d.keys())

            if inserted_flag:
                sorted_keys = sorted(d.keys())
                inserted_flag = False

            l = bisect.bisect_left(sorted_keys, para[1])
            r = bisect.bisect_right(sorted_keys, para[2])

            for i in range(l, r):
                print("{} {}".format(sorted_keys[i], d[sorted_keys[i]]))

main()

Submission status: Accepted

Solution code:
# Solved by QBnewb
# Discretization
# off-line

q = int(input())
s = []
rs = [] # for discretization

# download the input
for i in range(q):
    s.append(input().split())
    if s[i][0] == '3':
        rs.append(s[i][1])
        rs.append(s[i][2])
    else:
        rs.append(s[i][1])

rs = sorted(list(set(rs)))
index = {rs[i]:i for i in range(len(rs))} # discretization
d = [None for i in range(len(rs))] # discrete dictionary
for i in range(q):
    op, key = int(s[i][0]), s[i][1]
    idx = index[key]
    if op == 0:
        d[idx] = s[i][2]
    elif op == 1:
        if d[idx] ==None:
            print(0)
        else:
            print(d[idx])
    elif op == 2:
        d[idx] = None
    else:
        l = idx
        r = index[s[i][2]]
        for j in range(l, r+1):
            if d[j] != None:
                print(rs[j], d[j])

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right,insort_left

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

Submission status: Accepted

Solution code:
# AOJ ITP2_8_C: Map: Range Search
# Python3 2018.6.24 bal4u

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

Submission status: Accepted

Solution code:
import bisect

q = int(input())
M = {}
sortedList = []

for i in range(q):
    query, *inp = input().split()
    key = inp[0]

    # insert
    if query == "0":
        x = int(inp[1])

        if key not in M:
            bisect.insort_left(sortedList, key)

        M[key] = x


    # get
    elif query == "1":
        if key in M:
            if M[key] != None:
                print(M[key])
            else:
                print(0)
        else:
            print(0)

    # delete
    elif query == "2":
        if key in M:
            M[key] = None

    # dump
    else:
        L = inp[0]
        R = inp[1]

        index_left = bisect.bisect_left(sortedList, L)
        index_right = bisect.bisect_right(sortedList, R)

        for i in range(index_left, index_right):
            key_ans = sortedList[i]
            if M[key_ans] != None:
                print(key_ans, M[key_ans])

Submission status: Accepted

Solution code:
import bisect

keys=[]

q=int(input())
d={}

def find(x):
    index=bisect.bisect_left(keys,x)
    if index==len(keys):
        return -1
    if keys[index]==x:
        return index
    else:
        return -1


for _ in range(q):
    query=input().split(" ")
    if query[0]=="0":
        if find(query[1])!=-1:
            pass
        else:
            bisect.insort_left(keys, query[1])
        d[query[1]]=query[2]
    elif query[0]=="1":
        if find(query[1])!=-1:
            print(d[query[1]])
        else:
            print(0)
    elif query[0]=="2":
        while find(query[1])>=0:
            keys.pop(find(query[1]))
    else:
        L,R=query[1],query[2]
        indL=bisect.bisect_left(keys,L)
        indR=bisect.bisect_right(keys,R)
        for s in keys[indL:indR]:
            print(s,d[s])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_left
from typing import Dict, List


if __name__ == "__main__":
    num_query = int(input())
    d: Dict[str, int] = {}
    keys: List[str] = []

    for _ in range(num_query):
        op, *v = input().split()
        if ("0" == op):
            if v[0] not in d:
                insort_left(keys, v[0])
            d[v[0]] = int(v[1])
        elif ("1" == op):
            if v[0] in d:
                print(d[v[0]])
            else:
                print(0)
        elif ("2" == op):
            d[v[0]] = 0
        else:
            left_key = bisect_left(keys, v[0])
            right_key = bisect_right(keys, v[1], left_key)
            for k in range(left_key, right_key):
                if d[keys[k]] > 0:
                    print(keys[k], d[keys[k]])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Dictionary - Map: Range Search
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_8_C&lang=jp

"""
from bisect import insort, bisect_right, bisect_left

class Range_map:
    def __init__(self):
        self.rm = dict()
        self.lr = []

    def insert(self, x, y):
        if x not in self.rm:
            insort(self.lr, x)
        self.rm[x] = y

    def get(self, x):
        print(self.rm.get(x, 0))

    def delete(self, x):
        if x in self.rm:
            self.rm[x] = 0

    def dump(self, l, r):
        lb = bisect_left(self.lr, l)
        ub = bisect_right(self.lr, r)
        for i in range(lb, ub):
            k = self.lr[i]
            if k in self.rm and self.rm[k] != 0:
                print(f'{k} {self.rm[k]}')


rm = Range_map()
for _ in range(int(input())):
    op, x, y = (input() + ' 1').split()[:3]
    if op == '0':
        rm.insert(x, int(y))
    elif op == '1':
        rm.get(x)
    elif op == '2':
        rm.delete(x)
    else:
        rm.dump(x, y)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_left

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

S = {}
W = []

for i in range(q):
    if a[i][0] == '0':
        if not a[i][1] in S:
            insort_left(W,a[i][1])
        S[a[i][1]] = int(a[i][2])
    elif a[i][0] == '1':
        if a[i][1] in S:
            print(S[a[i][1]])
        else:
            print(0)
    elif a[i][0] == '2':
        if a[i][1] in S:
            S[a[i][1]] = 0
    else:
        L = bisect_left(W,a[i][1])
        R = bisect_right(W,a[i][2])
        for j in range(L,R):
            if S[W[j]] > 0:
                print(W[j],S[W[j]])

Submission status: Accepted

Solution code:
import bisect



q = int(input())

M = {}
list_key_sorted = []

for _ in range(q):
    
    command, *list_num = input().split()

    if   command == "0":
        # insert(key, x)
        key = list_num[0]
        x = int(list_num[1])

        if key not in M:
            bisect.insort_left(list_key_sorted, key)

        M[key] = x
    elif command == "1":
        # get(key)
        key = list_num[0]
        if key in M:
            if M[key] == None:
                print(0)
            else:
                print(M[key])
        else:
            print(0)
    elif command == "2":
        # delete(key)
        key = list_num[0]
        if key in M:
            M[key] = None
    elif command == "3":
        # dump(L, R)
        L = list_num[0]
        R = list_num[1]

        index_left = bisect.bisect_left(list_key_sorted, L)
        index_right = bisect.bisect_right(list_key_sorted, R)

        for index in range(index_left, index_right):
            key_ans = list_key_sorted[index]
            if M[key_ans] != None:
                print(key_ans, M[key_ans])
    else:
        raise

Submission status: Accepted

Solution code:
from bisect import *
import sys
n = int(input())
dic = {}
dic2 = {}
box = []
for i in range(n):
    a, b, *c = sys.stdin.readline().split()
    if a == '0':
        insort_left(box, b)
        dic[b] = int(c[0])
    elif a == '1':
        print(dic[b] if b in dic else 0)
    elif a == '2':
        if b in dic:
            del dic[b]
    else:
        L = bisect_left(box,b)
        R = bisect_right(box, c[0])
        while L<R:
            if box[L] in dic:
                print(box[L], dic[box[L]])
            L = bisect_right(box, box[L])

Submission status: Accepted

Solution code:
import bisect

M=[]
D=[]
N=[]
count=0

def insert(M,D,N,count,key,x):
    y=bisect.bisect_left(D,key)
    if y<count and D[y]==key:
        M[y][1]=x
        N[y]=x
    else:
        M.insert(y,[key,x])
        D.insert(y,key)
        N.insert(y,x)
        count+=1
    return M,D,N,count

def get(D,N,count,key):
    y=bisect.bisect_left(D,key)
    if y<count and D[y]==key:
        print(N[y])
    else:
        print(0)

def erase(M,D,N,count,key):
    y=bisect.bisect_left(D,key)
    if y<count and D[y]==key:
        M.pop(y)
        D.pop(y)
        N.pop(y)
        count-=1
    return M,D,N,count

def dump(M,D,N,L,R):
    s=bisect.bisect_left(D,L)
    e=bisect.bisect_right(D,R)
    if e-s>0:
        for i in range(s,e):
            print(M[i][0]+" "+str(M[i][1]))

q=int(input())
for i in range(q):
    query=list(map(str,input().split()))
    query[0]=int(query[0])
    if query[0]==0:
        M,D,N,count=insert(M,D,N,count,query[1],int(query[2]))
    elif query[0]==1:
        get(D,N,count,query[1])
    elif query[0]==2:
        M,D,N,count=erase(M,D,N,count,query[1])
    else:
        dump(M,D,N,query[1],query[2])

Submission status: Accepted

Solution code:
import sys
import bisect

n = int(input())
arr = []
lines = sys.stdin.readlines()
ans = [None] * n
d = {}
for i in range(n):
    q, *arg = lines[i].split()
    key = arg[0]
    idx = bisect.bisect_left(arr, arg[0])
    if q == '0':    # insert
        if idx == len(arr) or arr[idx] != key:
            arr.insert(idx, key)
        d[key] = arg[1]
    elif q == '1':  # get
        ans[i] = d[key] if idx != len(arr) and arr[idx] == key else '0'
    elif q == '2':  # delete
        if idx < len(arr) and arr[idx] == key:
            del arr[idx]
            del d[key]
    elif q == '3':  # dump L R
        r_idx = bisect.bisect_right(arr, arg[1])
        ans[i] = '\n'.join([f'{key_} {d[key_]}' for key_ in arr[idx:r_idx]]) if (r_idx - idx) != 0 else None

[print(x) for x in ans if x is not None]

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_left
q = int(input())
M = {}
tbl = []
for i in range(q):
    query, *x = input().split()
    if query == "0":
        x[1] = int(x[1])
        if x[0] not in M:
            insort_left(tbl, x[0])
        M[x[0]] = x[1]
    elif query == "1":
        print(M[x[0]] if x[0] in M and M[x[0]] != 0 else 0)
    elif query == "2":
        M[x[0]] = 0
    else:
        L = bisect_left( tbl, x[0])
        R = bisect_right(tbl, x[1])
        for i in range(L, R):
            if M[tbl[i]] != 0:
                print(tbl[i], M[tbl[i]])