結果

問題 No.759 悪くない忘年会にしような！
ユーザー lam6er
提出日時 2025-03-31 17:49:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 509 ms / 2,000 ms
コード長 2,000 bytes
コンパイル時間 347 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 117,692 KB
最終ジャッジ日時 2025-03-31 17:50:34
合計ジャッジ時間 13,943 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegmentTree:
    def __init__(self):
        self.max_T = 10000  # Maximum possible T
        self.size = self.max_T + 1  # 0 to 10000 inclusive
        self.n = 1
        while self.n < self.size:
            self.n <<= 1
        # Initialize tree with negative infinity
        self.tree = [-float('inf')] * (2 * self.n)

    def update(self, T, R):
        # Updates the value at position T to be the max between existing and R
        pos = T + self.n
        if self.tree[pos] >= R:
            return
        self.tree[pos] = R
        pos >>= 1
        while pos >= 1:
            new_val = max(self.tree[2 * pos], self.tree[2 * pos + 1])
            if self.tree[pos] == new_val:
                break
            self.tree[pos] = new_val
            pos >>= 1

    def query(self, L):
        # Returns the maximum R in [L, max_T]
        res = -float('inf')
        a = L
        b = self.max_T
        a += self.n
        b += self.n
        while a <= b:
            if a % 2 == 1:
                res = max(res, self.tree[a])
                a += 1
            if b % 2 == 0:
                res = max(res, self.tree[b])
                b -= 1
            a >>= 1
            b >>= 1
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    points = []
    for i in range(N):
        P = int(input[ptr])
        T = int(input[ptr+1])
        R = int(input[ptr+2])
        ptr +=3
        points.append( ( -P, -T, -R, i+1 ) )
    
    # Sort by descending P, then T, then R
    points.sort()
    seg = SegmentTree()
    ans = []
    for p in points:
        P_neg, T_neg, R_neg, idx = p
        T_real = -T_neg
        R_real = -R_neg
        # Query from T_real to max_T
        max_r = seg.query(T_real)
        if max_r >= R_real:
            continue
        ans.append(idx)
        seg.update(T_real, R_real)
    ans.sort()
    print('\n'.join(map(str, ans)))

if __name__ == "__main__":
    main()
0