結果
問題 | No.1675 Strange Minimum Query |
ユーザー | ansain |
提出日時 | 2021-09-10 21:52:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,913 bytes |
コンパイル時間 | 532 ms |
コンパイル使用メモリ | 87,220 KB |
実行使用メモリ | 121,160 KB |
最終ジャッジ日時 | 2023-09-02 17:02:08 |
合計ジャッジ時間 | 34,866 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 95 ms
71,964 KB |
testcase_01 | AC | 95 ms
71,992 KB |
testcase_02 | AC | 95 ms
71,892 KB |
testcase_03 | AC | 905 ms
98,024 KB |
testcase_04 | AC | 786 ms
97,016 KB |
testcase_05 | AC | 228 ms
84,648 KB |
testcase_06 | AC | 1,096 ms
110,980 KB |
testcase_07 | AC | 1,076 ms
110,280 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | AC | 766 ms
116,228 KB |
testcase_14 | AC | 1,023 ms
119,340 KB |
testcase_15 | AC | 992 ms
120,916 KB |
testcase_16 | AC | 98 ms
71,968 KB |
testcase_17 | AC | 469 ms
86,700 KB |
testcase_18 | AC | 576 ms
88,584 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 1,227 ms
115,052 KB |
testcase_23 | AC | 1,019 ms
98,660 KB |
testcase_24 | AC | 958 ms
102,008 KB |
testcase_25 | AC | 748 ms
93,612 KB |
testcase_26 | WA | - |
testcase_27 | AC | 964 ms
101,984 KB |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | AC | 1,320 ms
103,524 KB |
testcase_32 | AC | 1,664 ms
120,668 KB |
testcase_33 | AC | 1,733 ms
121,160 KB |
testcase_34 | AC | 1,622 ms
120,696 KB |
testcase_35 | AC | 1,508 ms
119,540 KB |
testcase_36 | AC | 1,482 ms
119,632 KB |
ソースコード
import sys from collections import defaultdict, Counter, deque from itertools import permutations, combinations, product, combinations_with_replacement, groupby, accumulate import operator from 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_tree def 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/20978786 class 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_identity self.oe = operator_identity self.fmm = func_monoid_monoid self.fmo = func_monoid_operator self.foo = func_operator_operator self.n = len(monoid_data) self.data = monoid_data * 2 for 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 # propagation for shift in range(index.bit_length()-1, 0, -1): i = index >> shift 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 # update self.data[index] = value self.lazy[index] = self.oe # recalculation i = index while i > 1: i //= 2 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.oe def effect(self, l, r, operator): l += self.n r += self.n # preparing indices indices = [] l0 = (l // (l & -l)) // 2 r0 = (r // (r & -r) - 1) // 2 while r0 > l0: indices.append(r0) r0 //= 2 while l0 > r0: indices.append(l0) l0 //= 2 while l0 and l0 != r0: indices.append(r0) r0 //= 2 if l0 == r0: break indices.append(l0) l0 //= 2 while r0: indices.append(r0) r0 //= 2 # propagation for 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 # effect while l < r: if l % 2: self.lazy[l] = self.foo(self.lazy[l], operator) l += 1 if r % 2: r -= 1 self.lazy[r] = self.foo(self.lazy[r], operator) l //= 2 r //= 2 # recalculation for 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.oe def folded(self, l, r): l += self.n r += self.n # preparing indices indices = [] l0 = (l // (l & -l)) // 2 r0 = (r // (r & -r) - 1) // 2 while r0 > l0: indices.append(r0) r0 //= 2 while l0 > r0: indices.append(l0) l0 //= 2 while l0 and l0 != r0: indices.append(r0) r0 //= 2 if l0 == r0: break indices.append(l0) l0 //= 2 while r0: indices.append(r0) r0 //= 2 # propagation for 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 # fold left_folded = self.me right_folded = self.me while l < r: if l % 2: left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l])) l += 1 if r % 2: r -= 1 right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded) l //= 2 r //= 2 return self.fmm(left_folded, right_folded) def main(): mod = 10**9+7 mod2 = 998244353 n,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**10]*n,10**10,-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) return print(*[seg.folded(i,i+1) for i in range(n)]) if __name__ == '__main__': main()