Submission 140155 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
140155	19/10/2019 16:26:55	otero1991	D - Dictionary search	Accepted	7031	78.7 MiB	Python 2.7 (PyPy)

Code

from bisect import bisect_left, bisect_right

words = []

st = []
for i in range(4 * 100010):
  st.append([])

def build(node, nodeL, nodeR):
  if nodeL < nodeR:
    m = (nodeL + nodeR) // 2
    build(2*node+1, nodeL, m)
    build(2*node+2, m+1, nodeR)

for i in range(nodeL, nodeR+1):
	  st[node].append(words[i][1])

st[node] = sorted(st[node])

def query(node, nodeL, nodeR, l, r, q):
  if l > nodeR or r < nodeL:
    return 0
  if nodeL >= l and nodeR <= r:
    lo = bisect_left(st[node], q)
    hi = bisect_right(st[node], q + '~')
    return hi-lo
  
  m = (nodeL + nodeR) // 2
  
  return query(2*node+1, nodeL, m, l, r, q) + query(2*node+2, m+1, nodeR, l, r, q);

def solve(p, q):
  lo = bisect_left(words, (p, ''))
  hi = bisect_right(words, (p + '~', 0))
  return query(0, 0, N-1, lo, hi-1, q)

N, Q = [int(s) for s in raw_input().split(' ')]

for i in range(N):
  a, b = raw_input().split(' ')
  words.append((a, b))

words = sorted(words, key=lambda x: x[0])

build(0, 0, N-1)

for i in range(Q):
	p, q = raw_input().split(' ')
	print(solve(p, q))

Judgement Details

Case#1 [31686656 bytes][203 ms]: ok 6 tokens
Case#2 [31690752 bytes][109 ms]: ok 5 tokens
Case#3 [31690752 bytes][93 ms]: ok 7 tokens
Case#4 [31690752 bytes][109 ms]: ok 7 tokens
Case#5 [31690752 bytes][109 ms]: ok 5 tokens
Case#6 [31694848 bytes][78 ms]: ok 5 tokens
Case#7 [31690752 bytes][109 ms]: ok 4 tokens
Case#8 [31690752 bytes][78 ms]: ok 4 tokens
Case#9 [38653952 bytes][906 ms]: ok 29714 tokens
Case#10 [39182336 bytes][906 ms]: ok 29714 tokens
Case#11 [41791488 bytes][2015 ms]: ok 100000 tokens
Case#12 [37515264 bytes][1406 ms]: ok 100000 tokens
Case#13 [33431552 bytes][156 ms]: ok 73 tokens
Case#14 [37781504 bytes][453 ms]: ok 1823 tokens
Case#15 [72753152 bytes][4781 ms]: ok 100000 tokens
Case#16 [71933952 bytes][4953 ms]: ok 100000 tokens
Case#17 [74743808 bytes][5421 ms]: ok 100000 tokens
Case#18 [73064448 bytes][5328 ms]: ok 100000 tokens
Case#19 [65732608 bytes][3921 ms]: ok 100000 tokens
Case#20 [65802240 bytes][3828 ms]: ok 100000 tokens
Case#21 [64729088 bytes][4031 ms]: ok 100000 tokens
Case#22 [64471040 bytes][4078 ms]: ok 100000 tokens
Case#23 [38420480 bytes][375 ms]: ok 396 tokens
Case#24 [72327168 bytes][5171 ms]: ok 100000 tokens
Case#25 [82526208 bytes][7031 ms]: ok 100000 tokens
Case#26 [73953280 bytes][3843 ms]: ok 100000 tokens
Case#27 [70643712 bytes][4296 ms]: ok 100000 tokens
Case#28 [43618304 bytes][1046 ms]: ok 9216 tokens

Matcom Online Grader