結果

問題 No.759 悪くない忘年会にしような！
ユーザー lam6er
提出日時 2025-03-20 20:53:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,788 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 82,820 KB
実行使用メモリ 130,148 KB
最終ジャッジ日時 2025-03-20 20:54:02
合計ジャッジ時間 30,452 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n = int(input())
stores = [tuple(map(int, input().split())) for _ in range(n)]

# Check for each restaurant i if there exists a restaurant j such that i is a subset of j (i is inferior to j)
# We need to determine if any of the three conditions hold for i being inferior to any j

# Sorted lists for each of the three conditions
# For condition checking i is inferior to j (i < j in any of the three ways)
# So we need to check if any j exists such that:
# 1. j.P > i.P and j.T >= i.T and j.R >= i.R
# 2. j.P >= i.P and j.T > i.T and j.R >= i.R
# 3. j.P >= i.P and j.T >= i.T and j.R > i.R

# To check these efficiently:
# For condition 1: sorted by P in ascending order. For i's P, look at higher P, check min T and R in that range
# If any has T >= i.T and R >= i.R → exists

# Similarly for other conditions

# Prepare sorted lists and their prefix minima for T and R
sorted_p_asc = sorted(stores, key=lambda x: (x[0], -x[1], -x[2]))
sorted_t_asc = sorted(stores, key=lambda x: (x[1], -x[0], -x[2]))
sorted_r_asc = sorted(stores, key=lambda x: (x[2], -x[0], -x[1]))

# For each sorted list, precompute prefix minima of T and R for condition checking

# For checking condition 1: j.P > i.P (sorted_p_asc), find the part where P > i.P, check if any j there has T >= i.T and R >= i.R
# Since the list is sorted by P ascending, the part where P > i.P is from some index to end
# The minima of T and R in suffix can be used: if min_T >= i.T and min_R >= i.R → yes

# Precompute suffix minima for T and R for sorted_p_asc
min_t_p_suffix = [0]*n
min_r_p_suffix = [0]*n
min_t = float('inf')
min_r = float('inf')
for i in reversed(range(n)):
    p, t, r = sorted_p_asc[i]
    min_t = min(min_t, t)
    min_r = min(min_r, r)
    min_t_p_suffix[i] = min_t
    min_r_p_suffix[i] = min_r

# Precompute suffix minima for P and R for sorted_t_asc (for condition 2)
min_p_t_suffix = [0]*n
min_r_t_suffix = [0]*n
min_p = float('inf')
min_r = float('inf')
for i in reversed(range(n)):
    t, p, r = sorted_t_asc[i][1], sorted_t_asc[i][0], sorted_t_asc[i][2]  # sorted by T, key is (T, -P, -R)
    min_p = min(min_p, p)
    min_r = min(min_r, r)
    min_p_t_suffix[i] = min_p
    min_r_t_suffix[i] = min_r

# Precompute suffix minima for P and T for sorted_r_asc (for condition 3)
min_p_r_suffix = [0]*n
min_t_r_suffix = [0]*n
min_p = float('inf')
min_t = float('inf')
for i in reversed(range(n)):
    r, p, t = sorted_r_asc[i][2], sorted_r_asc[i][0], sorted_r_asc[i][1]  # sorted by R, key is (R, -P, -T)
    min_p = min(min_p, p)
    min_t = min(min_t, t)
    min_p_r_suffix[i] = min_p
    min_t_r_suffix[i] = min_t

# Additionally, need the original store's P, T, R for each i

# Prepare lists for bisect
ps = [store[0] for store in sorted_p_asc]
ts = [store[1] for store in sorted_t_asc]
rs = [store[2] for store in sorted_r_asc]

ans = []

for idx in range(n):
    p_i, t_i, r_i = stores[idx]
    # Check condition 1: exists j where j.P > p_i and j.T >= t_i and j.R >= r_i
    # Find the first j in sorted_p_asc where j.P > p_i (since sorted ascending, all j from pos to end)
    pos_p = bisect.bisect_right(ps, p_i)
    exists1 = False
    if pos_p < n:
        # Check if the suffix from pos_p has min_T >= t_i and min_R >= r_i
        # Because suffix minima are computed, the minima can be checked
        min_t_suffix = min_t_p_suffix[pos_p]
        min_r_suffix = min_r_p_suffix[pos_p]
        if min_t_suffix >= t_i and min_r_suffix >= r_i:
            exists1 = True
    
    # Check condition 2: exists j where j.T > t_i and j.P >= p_i and j.R >= r_i
    pos_t = bisect.bisect_right(ts, t_i)
    exists2 = False
    if pos_t < n:
        # Check suffix minima of P and R
        # Here, sorted_t_asc is sorted by T ascending, P descending, R descending?
        # The suffix minima of P is the minimum in the suffix (since sorted by T asc, but for P we have to track)
        # sorted_t_asc is sorted by T, then by -P, then by -R → higher P comes first for the same T
        # suffix minima of P and R (we need min P >= p_i? No, need j.P >= p_i. If the min_P in suffix >= p_i → all have >= p_i)
        min_p_suffix = min_p_t_suffix[pos_t]
        min_r_suffix = min_r_t_suffix[pos_t]
        if min_p_suffix >= p_i and min_r_suffix >= r_i:
            exists2 = True
    
    # Check condition 3: exists j where j.R > r_i and j.P >= p_i and j.T >= t_i
    pos_r = bisect.bisect_right(rs, r_i)
    exists3 = False
    if pos_r < n:
        # Check suffix minima of P and T
        min_p_suffix = min_p_r_suffix[pos_r]
        min_t_suffix = min_t_r_suffix[pos_r]
        if min_p_suffix >= p_i and min_t_suffix >= t_i:
            exists3 = True
    
    if not (exists1 or exists2 or exists3):
        ans.append(idx + 1)

ans.sort()
print('\n'.join(map(str, ans)))
0