結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
![]() |
提出日時 | 2021-09-10 21:55:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,538 ms / 2,000 ms |
コード長 | 5,911 bytes |
コンパイル時間 | 419 ms |
コンパイル使用メモリ | 82,344 KB |
実行使用メモリ | 123,664 KB |
最終ジャッジ日時 | 2024-06-11 23:45:11 |
合計ジャッジ時間 | 31,520 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sysfrom collections import defaultdict, Counter, dequefrom itertools import permutations, combinations, product, combinations_with_replacement, groupby, accumulateimport operatorfrom math import sqrt, gcd, factorial#from math import isqrt, prod, comb #python3.8用(notpypy)#from bisect import bisect_left, bisect_right#from functools import lru_cache, reduce#from heapq import heappush, heappop, heapify, heappushpop, heapreplace#import numpy as np#import networkx as nx#from networkx.utils import UnionFind#from numba import njit, b1, i1, i4, i8, f8#numba例 @njit(i1(i4[:], i8[:, :]),cache=True) 引数i4配列、i8 2次元配列,戻り値i1#from scipy.sparse import csr_matrix#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, NegativeCycleError, maximum_bipartite_matching,maximum_flow, minimum_spanning_treedef input(): return sys.stdin.readline().rstrip()def divceil(n, k): return 1+(n-1)//k # n/kの切り上げを返すdef yn(hantei, yes='Yes', no='No'): print(yes if hantei else no)#ライブラリ参照https://atcoder.jp/contests/practice2/submissions/20978786class LazySegmentTree2:__slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):self.me = monoid_identityself.oe = operator_identityself.fmm = func_monoid_monoidself.fmo = func_monoid_operatorself.foo = func_operator_operatorself.n = len(monoid_data)self.data = monoid_data * 2for i in range(self.n-1, 0, -1):self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])self.lazy = [self.oe] * (self.n * 2)def replace(self, index, value):index += self.n# propagationfor shift in range(index.bit_length()-1, 0, -1):i = index >> shiftself.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])self.data[i] = self.fmo(self.data[i], self.lazy[i])self.lazy[i] = self.oe# updateself.data[index] = valueself.lazy[index] = self.oe# recalculationi = indexwhile i > 1:i //= 2self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )self.lazy[i] = self.oedef effect(self, l, r, operator):l += self.nr += self.n# preparing indicesindices = []l0 = (l // (l & -l)) // 2r0 = (r // (r & -r) - 1) // 2while r0 > l0:indices.append(r0)r0 //= 2while l0 > r0:indices.append(l0)l0 //= 2while l0 and l0 != r0:indices.append(r0)r0 //= 2if l0 == r0:breakindices.append(l0)l0 //= 2while r0:indices.append(r0)r0 //= 2# propagationfor i in reversed(indices):self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])self.data[i] = self.fmo(self.data[i], self.lazy[i])self.lazy[i] = self.oe# effectwhile l < r:if l % 2:self.lazy[l] = self.foo(self.lazy[l], operator)l += 1if r % 2:r -= 1self.lazy[r] = self.foo(self.lazy[r], operator)l //= 2r //= 2# recalculationfor i in indices:self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )self.lazy[i] = self.oedef folded(self, l, r):l += self.nr += self.n# preparing indicesindices = []l0 = (l // (l & -l)) // 2r0 = (r // (r & -r) - 1) // 2while r0 > l0:indices.append(r0)r0 //= 2while l0 > r0:indices.append(l0)l0 //= 2while l0 and l0 != r0:indices.append(r0)r0 //= 2if l0 == r0:breakindices.append(l0)l0 //= 2while r0:indices.append(r0)r0 //= 2# propagationfor i in reversed(indices):self.lazy[2*i] = self.foo(self.lazy[2*i], self.lazy[i])self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])self.data[i] = self.fmo(self.data[i], self.lazy[i])self.lazy[i] = self.oe# foldleft_folded = self.meright_folded = self.mewhile l < r:if l % 2:left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))l += 1if r % 2:r -= 1right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)l //= 2r //= 2return self.fmm(left_folded, right_folded)def main():mod = 10**9+7mod2 = 998244353n,q=map(int, input().split())lrb=[list(map(int, input().split())) for i in range(q)]lrb.sort(key=lambda x:x[2])seg=LazySegmentTree2([10**9]*n,10**9,-1,min,lambda x,y: x if y==-1 else y,lambda x,y: x if y==-1 else y)for l,r,b in lrb:seg.effect(l-1,r,b)for l,r,b in lrb:if seg.folded(l-1,r)!=b:print(-1)returnprint(*[seg.folded(i,i+1) for i in range(n)])if __name__ == '__main__':main()