結果

問題 No.1675 Strange Minimum Query
コンテスト
ユーザー wolgnik
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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