結果

問題 No.1675 Strange Minimum Query
ユーザー wolgnikwolgnik
提出日時 2021-09-10 21:45:55
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,358 bytes
コンパイル時間 454 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 205,004 KB
最終ジャッジ日時 2024-06-11 23:16:38
合計ジャッジ時間 33,038 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,768 KB
testcase_01 AC 40 ms
54,956 KB
testcase_02 AC 38 ms
53,164 KB
testcase_03 AC 1,468 ms
155,020 KB
testcase_04 AC 1,200 ms
152,408 KB
testcase_05 AC 156 ms
97,756 KB
testcase_06 AC 1,733 ms
174,260 KB
testcase_07 AC 1,771 ms
182,456 KB
testcase_08 AC 44 ms
60,156 KB
testcase_09 AC 68 ms
70,440 KB
testcase_10 AC 618 ms
135,228 KB
testcase_11 AC 165 ms
102,896 KB
testcase_12 AC 692 ms
143,372 KB
testcase_13 AC 671 ms
201,812 KB
testcase_14 AC 725 ms
201,704 KB
testcase_15 WA -
testcase_16 AC 39 ms
54,340 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
res = [10 ** 9] * N
event = []
qs = []
for i in range(Q):
  l, r, x = map(int, input().split())
  l -= 1
  qs.append((l, r, x))
  event.append((l, x, i))
  event.append((r, ~x, i))

import heapq
hpush = heapq.heappush
hpop = heapq.heappop

event.sort()
h = []
h2 = []

for i, x, k in event:
  while len(h) and len(h2) and h[0][1] == h2[0][1]:
    hpop(h)
    hpop(h2)
  if x >= 0:
    hpush(h, (x, k))
    res[i] = hpop(h)[0]
  else: hpush(h2, (~x, k))

class SparseTable:
  def calc(self, x, y): return min(x, y)
  def __init__(self, n, init_val, ide_ele):
    self.n = n
    k = n.bit_length()
    self.k = k
    self.ide_ele = ide_ele
    self.log_table = [[ide_ele] * n for _ in range(k + 1)]
    for i in range(n): self.log_table[0][i] = init_val[i]
    for i in range(k):
      d = 1 << i
      for j in range(n):
        if j + d >= n: break
        self.log_table[i + 1][j] = self.calc(self.log_table[i][j], self.log_table[i][j + d])
  def query(self, l, r):
    d = r - l
    if d < 0: return self.ide_ele
    if d == 1: return self.log_table[0][l]
    m = d.bit_length() - 1
    return self.calc(self.log_table[m][l], self.log_table[m][r - (1 << m)])

st = SparseTable(N, res, 10 ** 10)
for l, r, x in qs:
  if st.query(l, r) != x: break
else:
  print(*res)
  exit(0)
print(-1)
0