Submission #14613295


Source Code Expand

Copy
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(A, K, query):
    H, W = A.shape
    dp = np.zeros((H + 1, W + 1, K + 1), np.int64)
    for h in range(1, H + 1):
        for w in range(1, W + 1):
            dp[h, w] = dp[h - 1, w] + dp[h, w - 1] - dp[h - 1, w - 1]
            k = A[h - 1, w - 1]
            dp[h, w, k] += 1

    for i in range(len(query)):
        t, a, b, c, d = query[i]
        a, b, c, d = a - 1, b - 1, c - 1, d - 1
        if t == 1:
            if a + b > c + d:
                a, b, c, d = c, d, a, b
            k1, k2 = A[a, b], A[c, d]
            A[a,b], A[c,d] = k2,k1
            if k1 == k2:
                continue
            if a == c:
                dp[a + 1:, b + 1, k1] -= 1
                dp[a + 1:, b + 1, k2] += 1
            elif b == d:
                dp[a + 1, b + 1:, k1] -= 1
                dp[a + 1, b + 1:, k2] += 1
        elif t == 2:
            count = dp[c + 1, d + 1] + dp[a, b] - dp[a, d + 1] - dp[c + 1, b]
            k = K - np.argmax(count[::-1])
            print(k, count[k])

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i4[:, :], i4, i4[:, :]))
    cc.compile()

from my_module import main

N, M, K = map(int, readline().split())
A = np.array([list(map(int, readline().split())) for _ in range(N)], np.int32)
Q = int(readline())
query = np.array(read().split(), np.int32).reshape(Q, 5)

main(A, K, query)

Submission Info

Submission Time
Task C - 宝探し 2
User maspy
Language Python (3.8.2)
Score 100
Code Size 1750 Byte
Status
Exec Time 834 ms
Memory 231044 KB

Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 00-sample-00, 00-sample-01, 10-random_small-00, 10-random_small-01, 10-random_small-02, 10-random_small-03, 10-random_small-04, 10-random_small-05, 10-random_small-06, 10-random_small-07, 10-random_small-08, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 30-max_query-00, 30-max_query-01, 30-max_query-02
Case Name Status Exec Time Memory
00-sample-00 113 ms 26700 KB
00-sample-01 115 ms 27104 KB
10-random_small-00 196 ms 34192 KB
10-random_small-01 114 ms 27188 KB
10-random_small-02 137 ms 28788 KB
10-random_small-03 121 ms 28288 KB
10-random_small-04 217 ms 46612 KB
10-random_small-05 236 ms 48544 KB
10-random_small-06 121 ms 28420 KB
10-random_small-07 181 ms 38868 KB
10-random_small-08 124 ms 34996 KB
20-random_large-00 827 ms 228924 KB
20-random_large-01 822 ms 228692 KB
20-random_large-02 828 ms 229348 KB
20-random_large-03 834 ms 228620 KB
20-random_large-04 827 ms 231044 KB
30-max_query-00 602 ms 228724 KB
30-max_query-01 603 ms 229028 KB
30-max_query-02 607 ms 230128 KB