oj.uz

Submission #379973

# Submission time Handle Problem Language Result Execution time Memory
379973 2021-03-19T21:14:20 Z nigus Selling RNA Strands (JOI16_selling_rna) Python 3
10 / 100
 1500 ms 132420 KB 
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3948 KB Output is correct
2 Correct 29 ms 3948 KB Output is correct
3 Correct 30 ms 3948 KB Output is correct
4 Correct 29 ms 3820 KB Output is correct
5 Correct 29 ms 3948 KB Output is correct
6 Correct 29 ms 3948 KB Output is correct
7 Correct 29 ms 3948 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1612 ms 132420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1519 ms 64576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3948 KB Output is correct
2 Correct 29 ms 3948 KB Output is correct
3 Correct 30 ms 3948 KB Output is correct
4 Correct 29 ms 3820 KB Output is correct
5 Correct 29 ms 3948 KB Output is correct
6 Correct 29 ms 3948 KB Output is correct
7 Correct 29 ms 3948 KB Output is correct
8 Execution timed out 1612 ms 132420 KB Time limit exceeded
9 Halted 0 ms 0 KB -