結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | norioc |
提出日時 | 2024-02-24 01:19:16 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,624 bytes |
コンパイル時間 | 596 ms |
コンパイル使用メモリ | 81,572 KB |
実行使用メモリ | 65,804 KB |
最終ジャッジ日時 | 2024-02-24 01:19:22 |
合計ジャッジ時間 | 5,024 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
ソースコード
from atcoder.lazysegtree import LazySegTree class Compression: def __init__(self, iterable): self.xs = sorted(set(iterable)) self.n = len(self.xs) self.x2i = {} for i, x in enumerate(self.xs): self.x2i[x] = i def __len__(self): return self.n def index(self, x): """x のインデックスを返す""" return self.x2i[x] def value(self, index): """インデックスに対応する値を返す""" return self.xs[index] # 値データ S = int # 遅延データ F = int # 値データを合成 def op(a: S, b: S) -> S: # 使わない return 0 # 遅延データを値データに反映 : f(x) def mapping(f: F, x: S) -> S: if f == 0: return x return f # 遅延データを伝搬 # 二つの遅延データを合成 : (f . g) def composition(f: F, g: F) -> F: if f == 0: return g return f N, A = map(int, input().split()) X = list(map(int, input().split())) ss = set(X) T = int(input()) segs = [] for _ in range(T): L, R = map(int, input().split()) segs.append((L, R)) ss.add(L) ss.add(R) comp = Compression(ss) # 単位元 e : 全ての a に対して op(a, e) = op(e, a) = a を満たす # 恒等写像 id : 全ての a に対して mapping(id, a) = a を満たす lsegt = LazySegTree( op=op, e=0, mapping=mapping, composition=composition, id_=0, v=[-1] * len(comp)) for i, (l, r) in enumerate(segs): li = comp.index(l) ri = comp.index(r) lsegt.apply(li, ri+1, i+1) ans = [lsegt.get(comp.index(x)) for x in X] print(*ans, sep='\n')