Ruudukko

# completes tests 1 and 2, but not 3
import random
import time
import sys
from typing import Generator, TypeVar
import itertools
 
 
def I():
    return map(int, input().split())
 
 
# DIVISOR = 10**9 + 7
 
_V = TypeVar("_V")
 
test_N = 1000
test_seed = 1001
# seed is 1001
test_expected_results = {
    100: 773224951,
    200: 452330452,
    300: 37161558,
    400: 250332178,
    1000: 298053617
}
 
 
def test():
    n = test_N
 
    def text_gen():
        yield str(n)
        random.seed(test_seed)
        for i in range(n):
            yield " ".join((str(random.randint(1, n * n)) for _ in range(n)))
 
    return iter(list(text_gen())).__next__
 
 
# input = test()
timer_init = time.perf_counter()
 
 
class Node:
    # ended up unused
    "Binary Search Tree node"
 
    def __init__(self, parent: "Node|None", left: "Node|None", right: "Node|None", key: "int|float"):
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right
        self.values = []
        self.marker = 0
        pass
 
    def Get(self) -> "list":
        return self.values
        ...
 
    def Add(self, value):
        self.values.append(value)
 
    def next(self):
        if self.marker == 0:
            self.marker += 1
            if self.left:
                return self.left
        if self.marker == 1:
            self.marker += 1
            if self.right:
                return self.right
        self.marker = 0
        return self.parent
 
 
class BST:
    # ended up unused
    def __init__(self, middle: float):
        self.root = Node(None, None, None, middle)
 
    def Insert(self, key: "int | float", value: "_V"):
 
        node, pos = self.search(key)
        if pos == 1:
            node.left = Node(node, None, None, key)
            node.left.Add(value)
        elif pos == 2:
            node.right = Node(node, None, None, key)
            node.right.Add(value)
        else:
            node.Add(value)
 
    # def Get(self, key: "int | float") -> "Node":
    #     ...
 
    def Iter(self) -> "Generator[Node,None,None]":
        node = self.root
        while 1:
            new = node.next()
            if new is None:
                break
            if node.marker == 0:
                # new is parent
                if new.marker == 1:
                    # node is left
                    yield new
            elif new.left is None:
                yield new
            # elif node.marker == 1:
            #     # new is right child
            node = new
 
    def Iter_Values(self):
        # for node in self.Iter():
        #     for x, y in node.Get():
        #         yield node.key, x, y
        return ((node.key, v) for node in self.Iter() for v in node.Get())
 
    def search(self, key: "int|float") -> "tuple[Node, int]":
        """returns a node and a number.
        0 means the node has the wanted value,
        1 means the value doesn't exist but would be the node's left branch if inserted,
        2 means the same as 1 but for the right branch."""
        # no recursion
        current = self.root
        while 1:
            if key < current.key:
                if current.left:
                    current = current.left
                else:
                    return current, 1
            elif key > current.key:
                if current.right:
                    current = current.right
                else:
                    return current, 2
            else:
                return current, 0
 
 
def timer(desc: "str", prev: "float"):
    t = time.perf_counter()
    print(desc, t - prev, file=sys.stderr)
    return t
 
 
def main():
    DIVISOR = 10**9 + 7
 
    timer_0 = time.perf_counter()
    n, = I()
    grid = [list(I()) for _ in range(n)]
    sett = list((grid[y][x], x, y) for y in range(n) for x in range(n))
    # sett = set((a, x, y) for (y, x), a in zip(itertools.product(range(n), repeat=2), itertools.chain(*(I() for _ in range(n)))))
 
    timer_1 = timer("timer 1:", timer_0)
    line_row = [0] * n
    line_row_last = [1] * n
    line_col = [0] * n
    line_col_last = [1] * n
    line_row_added = [0] * n
    line_col_added = [0] * n
 
    timer_2 = timer("timer 2:", timer_1)
    sor = sorted(sett, key=lambda x: x[0])
    timer_3 = timer("sorting:", timer_2)
 
    total = 0
    for number, x, y in sor:
        if number != line_row_last[y]:
            line_row_last[y] = number
            line_row[y] += line_row_added[y]
            line_row_added[y] = 0
        if number != line_col_last[x]:
            line_col_last[x] = number
            line_col[x] += line_col_added[x]
            line_col_added[x] = 0
 
        value = (line_col[x] + line_row[y] + 1) % DIVISOR
        line_row_added[y] += value
        line_col_added[x] += value
        total += value
 
    # total = sum(calculate_routes(y, x, k)for k, x, y in sor)
    # total = sum(calculate_routes_full(*s)for s in sor)
    timer_4 = timer("timer 4:", timer_3)
 
    return total % DIVISOR
 
 
def old_iteration(n, grid, exists_row, exists_all, calculate_routes):
    for a in range(1, n * n + 1):
        if a not in exists_all:
            continue
        for y in range(n):
            if a not in exists_row[y]:
                continue
            x = -1
            try:
                while True:
                    x = grid[y].index(a, x + 1)
                    calculate_routes(y, x, a)
            except ValueError:
                pass
 
 
timer_start = time.perf_counter()
w = main()
print(w)
# 100: 773224951
# 200: 452330452
timer_end = time.perf_counter()
print("time:", timer_end - timer_start,
      ("\ncorrect" if w == test_expected_results[test_N] else "\ndifferent") if test_N in test_expected_results.keys() else "no data",
      #   "\ninit:", timer_start - timer_init,
      "\nseed:", test_seed,
      file=sys.stderr)

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

timer 1: 0.00020664592739194632
timer 2: 2.742407377809286e-05
sorting: 2.7357949875295162...

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

timer 1: 0.00019310100469738245
timer 2: 2.7289963327348232e-05
sorting: 2.771697472780943...

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

timer 1: 0.00018205400556325912
timer 2: 2.65931012108922e-05
sorting: 2.6968889869749546e...

Test 4

Group: 2, 3

Verdict: ACCEPTED

timer 1: 0.0109414680628106
timer 2: 6.188603583723307e-05
sorting: 0.0036987699568271637...

Test 5

Group: 2, 3

Verdict: ACCEPTED

timer 1: 0.010855545056983829
timer 2: 6.181898061186075e-05
sorting: 0.00383433501701802...

Test 6

Group: 2, 3

Verdict: ACCEPTED

timer 1: 0.012620743014849722
timer 2: 6.153108552098274e-05
sorting: 0.01132322195917368...

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 3

Verdict: TIME LIMIT EXCEEDED