提出 #73540386

---

ソースコード 拡げる

# https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            if s < self.tree[i]:
                s = self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i

def solve(N,XYZ):
    XYZ.sort(key=lambda x: (-x[0],-x[1],-x[2]))
    MY = max(y for _, y, _ in XYZ)
    bit = Bit(MY)
    ans = 0
    i = 0
    while i < N:
        j = i
        A = []
        x = XYZ[i][0]
        while j < N and XYZ[j][0] == x:
            A.append(XYZ[j])
            j += 1
        for _,y,z in A:
            B = MY - y + 1
            if bit.sum(B-1) <= z:
                ans += 1
        P = {}
        for _,y,z in A:
            if y not in P or P[y] < z:
                P[y] = z
        for y,z in P.items():
            C = MY - y + 1
            bit.add(C,z)
        i = j
    return ans
for _ in range(int(input())):
    N = int(input())
    XYZ = [list(map(int,input().split())) for _ in range(N)]
    print(solve(N,XYZ))

提出情報

ジャッジ結果