結果
問題 | No.1675 Strange Minimum Query |
ユーザー | ansain |
提出日時 | 2021-09-10 21:55:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,817 ms / 2,000 ms |
コード長 | 5,911 bytes |
コンパイル時間 | 1,608 ms |
コンパイル使用メモリ | 86,696 KB |
実行使用メモリ | 120,800 KB |
最終ジャッジ日時 | 2023-09-02 17:11:32 |
合計ジャッジ時間 | 36,709 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 99 ms
71,476 KB |
testcase_01 | AC | 95 ms
71,192 KB |
testcase_02 | AC | 96 ms
71,556 KB |
testcase_03 | AC | 1,007 ms
97,964 KB |
testcase_04 | AC | 777 ms
96,528 KB |
testcase_05 | AC | 229 ms
84,068 KB |
testcase_06 | AC | 1,097 ms
110,484 KB |
testcase_07 | AC | 1,059 ms
110,172 KB |
testcase_08 | AC | 109 ms
77,152 KB |
testcase_09 | AC | 179 ms
79,148 KB |
testcase_10 | AC | 655 ms
97,828 KB |
testcase_11 | AC | 356 ms
89,024 KB |
testcase_12 | AC | 698 ms
99,404 KB |
testcase_13 | AC | 756 ms
115,560 KB |
testcase_14 | AC | 1,040 ms
119,184 KB |
testcase_15 | AC | 995 ms
120,800 KB |
testcase_16 | AC | 96 ms
71,472 KB |
testcase_17 | AC | 475 ms
86,208 KB |
testcase_18 | AC | 564 ms
88,152 KB |
testcase_19 | AC | 612 ms
95,836 KB |
testcase_20 | AC | 1,099 ms
104,948 KB |
testcase_21 | AC | 1,063 ms
102,560 KB |
testcase_22 | AC | 1,231 ms
114,836 KB |
testcase_23 | AC | 1,003 ms
98,496 KB |
testcase_24 | AC | 999 ms
101,776 KB |
testcase_25 | AC | 757 ms
93,652 KB |
testcase_26 | AC | 551 ms
90,016 KB |
testcase_27 | AC | 967 ms
101,792 KB |
testcase_28 | AC | 603 ms
93,752 KB |
testcase_29 | AC | 511 ms
93,060 KB |
testcase_30 | AC | 506 ms
89,368 KB |
testcase_31 | AC | 1,311 ms
103,656 KB |
testcase_32 | AC | 1,681 ms
120,572 KB |
testcase_33 | AC | 1,817 ms
120,704 KB |
testcase_34 | AC | 1,599 ms
120,352 KB |
testcase_35 | AC | 1,505 ms
119,064 KB |
testcase_36 | AC | 1,557 ms
119,344 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**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) return print(*[seg.folded(i,i+1) for i in range(n)]) if __name__ == '__main__': main()