class Node:
def __init__(self, letter):
self.letter = letter
self.val = 0
self.children = {}
def add(self, string, i):
self.val += 1
if i == len(string): return
if string[i] in self.children:
self.children[string[i]].add(string, i + 1)
else:
self.children[string[i]] = Node(string[i])
self.children[string[i]].add(string, i + 1)
def count(self, string, i):
if i == len(string): return self.val
if string[i] in self.children:
return self.children[string[i]].count(string, i + 1)
return 0
class WordTree:
def __init__(self):
self.root = Node("")
self.words = []
def add(self, word):
self.words.append(word)
self.root.add(word, 0)
def query(self, word):
return self.root.count(word, 0)
def merge(self, tree):
for word in tree.words:
self.add(word)
self.words.append(word)
class SegNode:
def __init__(self, left, right, arr):
self.left, self.right = left, right
self.leaf = self.left == self.right
if self.leaf:
self.tree = WordTree()
self.tree.add(arr[left])
else:
mid = (left + right) / 2
self.children = [
SegNode(left, mid, arr),
SegNode(mid + 1, right, arr)
]
self.tree = WordTree()
for c in self.children:
for w in c.tree.words:
self.tree.add(w)
def query(self, word, left, right):
if self.left >= left and self.right <= right:
return self.tree.query(word)
elif self.left > right or self.right < left:
return 0
else:
return sum([
c.query(word, left, right) for c in self.children
])
class SegmentTree:
def __init__(self, arr):
self.n = len(arr)
self.root = SegNode(0, self.n - 1, arr)
def query(self, word, left, right):
return self.root.query(word, left, right)
(n, q) = map(int, input().split())
ordlista = []
for _ in range(n):
ordlista.append(input())
ordlista.sort()
rev = [i[::-1] for i in ordlista]
T = SegmentTree(rev)
def query(start, end):
end = end[::-1]
# binary search left
low = 0
high = n
while high - low != 1:
mid = (low + high) / 2
if ordlista[mid][:len(start)] >= start:
high = mid
else:
low = mid
if ordlista[low][:len(start)] >= start:
left = low
else:
left = high
# binary search right
low = 0
high = n - 1
while high - low != 1:
mid = (low + high) / 2
if ordlista[mid][:len(start)] <= start:
low = mid
else:
high = mid
if ordlista[high][:len(start)] <= start:
right = high
else:
right = low
#print(left, right, "HEJ")
return T.query(end, left, right)
for Q in range(q):
start, end = input().split()
print(query(start, end))
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
20296 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
20424 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
41 ms |
20424 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
20296 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
