Problem:

Multi-Map

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 multiple elements can have equivalent keys.

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

  
get($key$): Print all values with the specified $key$.

  
delete($key$): Delete all elements 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 values in the order of insertions.

  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 in ascending order of the keys, in case of a tie, in the order of insertions.

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 get operations does not exceed $500,000$

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

Sample Input 1

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

Sample Output 1

1
6
4
white 5



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


Sample output:
1
6
4
white 5

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()
        self.count = 0

    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):
        if key in self.tree:
            values = self.tree.get(key)
            values += (value,)
        else:
            values = (value,)
        self.tree.put(key, values)
        self.count += 1

    def __delitem__(self, key):
        if key in self.tree:
            values = self.tree.get(key)
            self.tree.put(key, tuple())
            self.count -= len(values)
        else:
            raise IndexError('key {} not found in map'.format(key))

    def __len__(self):
        return self.count

    def items(self):
        for k, v in self.tree:
            for x in v:
                yield (k, x)

    def range(self, min_, max_):
        for k, v in self.tree.range(min_, max_):
            for x in v:
                yield (k, x)


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:
                for value in m[key]:
                    print(value)
            except IndexError:
                pass
        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_D: Multi-Map
# Python3 2018.6.24 bal4u

import bisect
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:
			dict[ki] = []
			insort_left(keytbl, ki)
		dict[ki].append(int(a[2]))
	elif a[0] == '1' and ki in dict and dict[ki] != []: print(*dict[ki], sep='\n')
	elif a[0] == '2' and ki in dict: dict[ki] = []
	elif a[0] == '3':
		L = bisect_left (keytbl, a[1])
		R = bisect_right(keytbl, a[2])
		for j in range(L, R):
			for k in dict[keytbl[j]]:
				print(keytbl[j], k)

Submission status: Accepted

Solution code:
# AOJ ITP2_8_D: Multi-Map
# 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:
			dict[ki] = []
			insort_left(keytbl, ki)
		dict[ki].append(int(a[2]))
	elif a[0] == '1':
		if ki in dict and dict[ki] != []: print(*dict[ki], sep='\n')
	elif a[0] == '2':
		if ki in dict: dict[ki] = []
	else:
		L = bisect_left (keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			for k in dict[keytbl[j]]: print(keytbl[j], k)

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 not order[1] in dic:
            dic[order[1]] = []
            insort(l,order[1])
        dic[order[1]].append(int(order[2]))
    elif order[0] == "1":
        if order[1] in dic:
            for i in dic[order[1]]:
                print(i)
    elif order[0] == "2":
        if order[1] in dic:
            dic[order[1]] = []

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

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict

def main():

    q = int(input())
    d = defaultdict(list)

    inserted_flag = False
    sorted_keys = None

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

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

        elif para[0] == "1":
            if para[1] in d.keys():
                for i in range(len(d[para[1]])):
                        print(d[para[1]][i])
                        
        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):
                for j in range(len(d[sorted_keys[i]])):
                    print("{} {}".format(sorted_keys[i], d[sorted_keys[i]][j]))

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 = [[] 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].append(s[i][2])
    elif op == 1:
        for item in d[idx]:
            print(item)
    elif op == 2:
        d[idx].clear()
    else:
        l = idx
        r = index[s[i][2]]
        for j in range(l, r+1):
            for item in d[j]:
                print(rs[j], item)

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:
            dict[ki] =[]
            insort_left(keytbl,ki)
        dict[ki].append(int(a[2]))
    elif a[0] == "1":
        if ki in dict and dict[ki] != []:print(*dict[ki],sep="\n")
    elif a[0] == "2":
        if ki in dict: dict[ki] = []
    else:
        L =bisect_left(keytbl,a[1])
        R = bisect_right(keytbl,a[2],L)
        for j in range(L,R):
            for k in dict[keytbl[j]]:
                print(keytbl[j],k)

Submission status: Accepted

Solution code:
# AOJ ITP2_8_D: Multi-Map
# 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:
			dict[ki] = []
			insort_left(keytbl, ki)
		dict[ki].append(int(a[2]))
	elif a[0] == '1':
		if ki in dict and dict[ki] != []: print(*dict[ki], sep='\n')
	elif a[0] == '2':
		if ki in dict: dict[ki] = []
	else:
		L = bisect_left (keytbl, a[1])
		R = bisect_right(keytbl, a[2], L)
		for j in range(L, R):
			for k in dict[keytbl[j]]: print(keytbl[j], k)

Submission status: Accepted

Solution code:
import bisect

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

for value 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] = []

        M[key].append(x)

    # get
    elif query == "1":
        if key in M:
            if M[key]:
                for value in M[key]:
                    print(value)

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

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

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

        for value in range(index_left, index_right):
            keyAns = sortedList[value]
            if M[keyAns]:
                for valueAns in M[keyAns]:
                    print(keyAns, valueAns)

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:
            item=d[query[1]]
        else:
            bisect.insort_left(keys, query[1])
            item=[]
        item.append(query[2])
        d[query[1]]=item
    elif query[0]=="1":
        if find(query[1])!=-1:
            for item in d[query[1]]:
                print(item)
    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]:
            for item in d[s]:
                print(s,item)

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, List[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]] = []
            d[v[0]].append(int(v[1]))
        elif ("1" == op):
            if v[0] in d:
                for elem in d[v[0]]:
                    print(elem)
        elif ("2" == op):
            if v[0] in d:
                d[v[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):
                for elem in d[keys[k]]:
                    print(keys[k], elem)

Submission status: Accepted

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

"""
from bisect import insort, bisect_right, bisect_left

class Multi_map:
    def __init__(self):
        self.mm = dict()
        self.lr = []

    def insert(self, x, y):
        if x in self.mm:
            self.mm[x].append(y)
        else:
            self.mm[x] = [y]
            insort(self.lr, x)

    def get(self, x):
        if x in self.mm and self.mm[x] != []:
            print(*self.mm[x], sep='\n')

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

    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]
            for v in self.mm[k]:
                print(f'{k} {v}')


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

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] = []

        M[key].append(x)
    elif command == "1":
        # get(key)
        key = list_num[0]
        if key in M:
            if M[key]:
                for value in M[key]:
                    print(value)
    elif command == "2":
        # delete(key)
        key = list_num[0]
        if key in M:
            M[key] = []
    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]:
                for value_ans in M[key_ans]:
                    print(key_ans, value_ans)
    else:
        raise

Submission status: Accepted

Solution code:
from bisect import *
n = int(input())
dic = {}
dic2 = {}
box = []
for i in range(n):
    a, b, *c = input().split()
    if a == '0':
        insort_left(box, b)
        if b in dic:
            temp = dic[b]
            dic[b] = temp + [int(c[0])]
        else:
            dic[b] = [int(c[0])]
    elif a == '1':
        if b in dic:
            pri = []
            for i in dic[b]:
                pri.append(str(i))
            print("\n".join(pri))
    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:
                for i in dic[box[L]]:
                    print(box[L], i)
            L = bisect_right(box, box[L])

Submission status: Accepted

Solution code:
import bisect

M={}
D=[]

def insert(M,D,key,x):
    if key not in M:
        M[key]=[]
        bisect.insort_left(D,key)
    M[key].append(x)
    return M,D

def get(M,D,key):
    if key in M and M[key]!=[]:
        print('\n'.join(map(str,M[key])))

def erase(M,D,key):
    if key in M:
        M[key]=[]
    return M,D

def dump(M,D,L,R):
    s=bisect.bisect_left(D,L)
    e=bisect.bisect_right(D,R)
    if e-s>0:
        #ループを使わずにできる方法を考える
        for i in range(s,e):
            for j in M[D[i]]:
                print(D[i],j)

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=insert(M,D,query[1],int(query[2]))
    elif query[0]==1:
        get(M,D,query[1])
    elif query[0]==2:
        M,D=erase(M,D,query[1])
    else:
        dump(M,D,query[1],query[2])

Submission status: Accepted

Solution code:
import sys
import bisect
from collections import defaultdict

n = int(input())
arr = []
d = defaultdict(list)
lines = sys.stdin.readlines()
ans = [None] * n

for i in range(n):
    q, *arg = lines[i].split()
    key = arg[0]
    l_idx = bisect.bisect_left(arr, arg[0])
    r_idx = bisect.bisect_right(arr, arg[0])
    if q == '0':    # insert
        if l_idx == len(arr) or arr[l_idx] != key:
            arr.insert(l_idx, key)
        d[key].append(arg[1])
    elif q == '1':  # get
        if l_idx != r_idx:
            ans[i] = '\n'.join(d[key])
    elif q == '2':  # delete
        arr[l_idx:r_idx] = []
        if l_idx != r_idx:
            del d[key]
    elif q == '3':  # dump L R
        r_idx = bisect.bisect_right(arr, arg[1])
        if l_idx != r_idx:
            keys = arr[l_idx:r_idx]
            ans[i] = '\n'.join(['\n'.join([f'{k} {x}' for x in d[k]]) for k in keys])

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