제출 #379973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379973		nigus	Selling RNA Strands (JOI16_selling_rna)	Cpython 3	10 / 100	1612 ms	132420 KiB

selling_rna

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))

• Subtask 1: 10 / 10
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40