結果
問題 | No.2650 [Cherry 6th Tune *] セイジャク |
ユーザー | StanMarsh |
提出日時 | 2024-02-23 22:37:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 955 ms / 2,500 ms |
コード長 | 16,133 bytes |
コンパイル時間 | 641 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 226,352 KB |
最終ジャッジ日時 | 2024-02-23 22:38:18 |
合計ジャッジ時間 | 26,427 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 151 ms
90,948 KB |
testcase_01 | AC | 146 ms
90,948 KB |
testcase_02 | AC | 352 ms
129,208 KB |
testcase_03 | AC | 308 ms
115,640 KB |
testcase_04 | AC | 711 ms
183,168 KB |
testcase_05 | AC | 613 ms
191,812 KB |
testcase_06 | AC | 397 ms
138,480 KB |
testcase_07 | AC | 610 ms
173,116 KB |
testcase_08 | AC | 341 ms
136,260 KB |
testcase_09 | AC | 955 ms
223,424 KB |
testcase_10 | AC | 923 ms
221,756 KB |
testcase_11 | AC | 910 ms
220,952 KB |
testcase_12 | AC | 874 ms
220,956 KB |
testcase_13 | AC | 923 ms
221,176 KB |
testcase_14 | AC | 918 ms
220,980 KB |
testcase_15 | AC | 955 ms
222,796 KB |
testcase_16 | AC | 804 ms
222,032 KB |
testcase_17 | AC | 829 ms
226,352 KB |
testcase_18 | AC | 801 ms
221,740 KB |
testcase_19 | AC | 815 ms
221,372 KB |
testcase_20 | AC | 805 ms
220,976 KB |
testcase_21 | AC | 797 ms
221,952 KB |
testcase_22 | AC | 890 ms
222,156 KB |
testcase_23 | AC | 821 ms
222,296 KB |
testcase_24 | AC | 767 ms
222,080 KB |
testcase_25 | AC | 776 ms
222,032 KB |
testcase_26 | AC | 765 ms
222,376 KB |
testcase_27 | AC | 777 ms
220,276 KB |
testcase_28 | AC | 745 ms
222,276 KB |
testcase_29 | AC | 769 ms
222,064 KB |
testcase_30 | AC | 725 ms
221,932 KB |
testcase_31 | AC | 804 ms
220,668 KB |
testcase_32 | AC | 463 ms
141,392 KB |
ソースコード
from random import getrandbits, randrange from string import ascii_lowercase, ascii_uppercase import sys from math import ceil, floor, sqrt, pi, factorial, gcd, log, log10, log2, inf, cos, sin from copy import deepcopy, copy from collections import Counter, deque, defaultdict from heapq import heapify, heappop, heappush from itertools import ( accumulate, chain, product, combinations, combinations_with_replacement, permutations, ) from bisect import bisect, bisect_left, bisect_right from functools import lru_cache, reduce from decimal import Decimal, getcontext from typing import List, Tuple, Optional inf = float("inf") class Inf: def __init__(self, value): self.value = value def __lt__(self, other): return False def __le__(self, other): if isinstance(other, Inf): return True return False def __gt__(self, other): if isinstance(other, Inf): return False return True def __ge__(self, other): return True def __eq__(self, other): return isinstance(other, Inf) and self.value == other.value def __repr__(self): return f"{self.value}" def __add__(self, other): return Inf(self.value) if isinstance(other, Inf) else self def __sub__(self, other): return Inf(self.value) if isinstance(other, Inf) else self def __mul__(self, other): return Inf(self.value) if isinstance(other, Inf) else self def ceil_div(a, b): return (a + b - 1) // b def isqrt(num): res = int(sqrt(num)) while res * res > num: res -= 1 while (res + 1) * (res + 1) <= num: res += 1 return res def int1(s): return int(s) - 1 from types import GeneratorType def bootstrap(f, stack=[]): def wrapped(*args, **kwargs): if stack: return f(*args, **kwargs) else: to = f(*args, **kwargs) while True: if type(to) is GeneratorType: stack.append(to) to = next(to) else: stack.pop() if not stack: break to = stack[-1].send(to) return to return wrapped import sys import os input = lambda: sys.stdin.readline().rstrip("\r\n") print = lambda *args, end="\n", sep=" ": sys.stdout.write( sep.join(map(str, args)) + end ) def II(): return int(input()) def MII(base=0): return map(lambda s: int(s) - base, input().split()) def LII(base=0): return list(MII(base)) def NA(): n = II() a = LII() return n, a def read_graph(n, m, base=0, directed=False, return_edges=False): g = [[] for _ in range(n)] edges = [] for _ in range(m): a, b = MII(base) if return_edges: edges.append((a, b)) g[a].append(b) if not directed: g[b].append(a) if return_edges: return g, edges return g def read_graph_with_weight(n, m, base=0, directed=False, return_edges=False): g = [[] for _ in range(n)] edges = [] for _ in range(m): a, b, w = MII() a, b = a - base, b - base if return_edges: edges.append((a, b, w)) g[a].append((b, w)) if not directed: g[b].append((a, w)) if return_edges: return g, edges return g def read_edges_from_ps(): ps = LII(1) edges = [] for i, p in enumerate(ps, 1): edges.append((p, i)) return edges def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = None def NI(): global tokens if tokens is None: tokens = iterate_tokens() return int(next(tokens)) def LNI(n): return [NI() for _ in range(n)] def yes(res): print("Yes" if res else "No") def YES(res): print("YES" if res else "NO") def pairwise(a): n = len(a) for i in range(n - 1): yield a[i], a[i + 1] def factorial(n): return reduce(lambda x, y: x * y, range(1, n + 1)) def cmin(dp, i, x): if x < dp[i]: dp[i] = x def cmax(dp, i, x): if x > dp[i]: dp[i] = x def alp_a_to_i(s): return ord(s) - ord("a") def alp_A_to_i(s): return ord(s) - ord("A") def alp_i_to_a(i): return chr(ord("a") + i) def alp_i_to_A(i): return chr(ord("A") + i) d4 = [(1, 0), (0, 1), (-1, 0), (0, -1)] d8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)] def ranges(n, m): return ((i, j) for i in range(n) for j in range(m)) def rangess(a, b, c): return ((i, j, k) for i in range(a) for j in range(b) for k in range(c)) def valid(i, j, n, m): return 0 <= i < n and 0 <= j < m def ninj(i, j, n, m): return [(i + di, j + dj) for di, dj in d4 if valid(i + di, j + dj, n, m)] def gen(x, *args): if len(args) == 1: return [x] * args[0] if len(args) == 2: return [[x] * args[1] for _ in [0] * args[0]] if len(args) == 3: return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]] if len(args) == 4: return [ [[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]] for _ in [0] * args[0] ] list2d = lambda a, b, v: [[v] * b for _ in range(a)] list3d = lambda a, b, c, v: [[[v] * c for _ in range(b)] for _ in range(a)] class Debug: def __init__(self, debug=False): self.debug = debug cur_path = os.path.dirname(os.path.abspath(__file__)) self.local = os.path.exists(cur_path + "/.cph") def get_ic(self): if self.debug and self.local: from icecream import ic return ic else: return lambda *args, **kwargs: ... class LazySegmentTree: def __init__(self, op, e, mapping, composition, id, n_a): self._n = len(n_a) if isinstance(n_a, list) else n_a self.op = op self.e = e self.mapping = mapping self.composition = composition self.id = id self.log = (self._n - 1).bit_length() self.size = 1 << self.log self.d = [e for _ in range(2 * self.size)] self.lz = [id for _ in range(self.size)] if isinstance(n_a, list): self.d[self.size : self.size + self._n] = n_a [self._update(i) for i in reversed(range(1, self.size))] def __repr__(self): l, r = 1, 2 res = [] def np_T(x): return [list(x) for x in zip(*x)] while r <= self.size: res.append(f"{np_T([self.d[l: r], self.lz[l: r]])}") l, r = r, r << 1 res.append(f"{self.d[l: r]}") return "\n".join(res) def set(self, p, x): p += self.size [self._push(p >> i) for i in reversed(range(1, self.log + 1))] self.d[p] = x [self._update(p >> i) for i in range(1, self.log + 1)] def get(self, p): p += self.size [self._push(p >> i) for i in reversed(range(1, self.log + 1))] return self.d[p] __setitem__ = set def __getitem__(self, k): if isinstance(k, slice): l = k.start if k.start is not None else 0 r = k.stop if k.stop is not None else self._n - 1 if l < 0: l += self._n if r < 0: r += self._n if l == 0 and r == self._n - 1: return self.all_prod() return self.prod(l, r + 1) return self.get(k) def prod(self, l, r): if l == r: return self.e l += self.size r += self.size for i in reversed(range(1, self.log + 1)): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) sml, smr = self.e, self.e while l < r: if l & 1: sml = self.op(sml, self.d[l]) l += 1 if r & 1: r -= 1 smr = self.op(self.d[r], smr) l >>= 1 r >>= 1 return self.op(sml, smr) def all_prod(self): return self.d[1] def apply_point(self, p, f): p += self.size [self._push(p >> i) for i in reversed(range(1, self.log + 1))] self.d[p] = self.mapping(f, self.d[p]) [self._update(p >> i) for i in range(1, self.log + 1)] def apply(self, l, r, f): if l == r: return l += self.size r += self.size for i in reversed(range(1, self.log + 1)): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) l2, r2 = l, r while l < r: if l & 1: self._all_apply(l, f) l += 1 if r & 1: r -= 1 self._all_apply(r, f) l >>= 1 r >>= 1 l, r = l2, r2 for i in range(1, self.log + 1): if ((l >> i) << i) != l: self._update(l >> i) if ((r >> i) << i) != r: self._update((r - 1) >> i) def _update(self, k): self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1]) def _all_apply(self, k, f): self.d[k] = self.mapping(f, self.d[k]) if k < self.size: self.lz[k] = self.composition(f, self.lz[k]) def _push(self, k): self._all_apply(2 * k, self.lz[k]) self._all_apply(2 * k + 1, self.lz[k]) self.lz[k] = self.id INF = 10**16 def sum2(x, y): return (x[0] + y[0], x[1] + y[1]) def add(f, x): return f + x def add2(f, x): return (x[0] + f * x[1], x[1]) def add_comp(f, g): return f + g def update(f, x): return f if f < INF else x def update_min(f, x): return min(f, x) def update2(f, x): return (f * x[1], x[1]) if f < INF else x def update_comp(f, g): return f if f < INF else g class SegmentTree: def __init__(self, n): self.update_cnt = 0 self.n = n self.size = 1 while self.size < n: self.size *= 2 self.node = [(self.update_cnt, 0) for i in range(2 * self.size - 1)] def apply(self, begin, end, val): self.update_cnt += 1 begin += self.size - 1 end += self.size - 1 while begin < end: if (end - 1) & 1: end -= 1 self.node[end] = (self.update_cnt, val) if (begin - 1) & 1: self.node[begin] = (self.update_cnt, val) begin += 1 begin = (begin - 1) // 2 end = (end - 1) // 2 def get(self, i): i += self.size - 1 val = self.node[i] while i > 0: i = (i - 1) // 2 val = max(val, self.node[i]) return val[1] __getitem__ = get class LazySegmentTree: def __init__(self, op, e, mapping, composition, id, n_a): self._n = len(n_a) if isinstance(n_a, list) else n_a self.op = op self.e = e self.mapping = mapping self.composition = composition self.id = id self.log = (self._n - 1).bit_length() self.size = 1 << self.log self.d = [e for _ in range(2 * self.size)] self.lz = [id for _ in range(self.size)] if isinstance(n_a, list): self.d[self.size : self.size + self._n] = n_a [self._update(i) for i in reversed(range(1, self.size))] def __repr__(self): l, r = 1, 2 res = [] def np_T(x): return [list(x) for x in zip(*x)] while r <= self.size: res.append(f"{np_T([self.d[l: r], self.lz[l: r]])}") l, r = r, r << 1 res.append(f"{self.d[l: r]}") return "\n".join(res) def set(self, p, x): p += self.size [self._push(p >> i) for i in reversed(range(1, self.log + 1))] self.d[p] = x [self._update(p >> i) for i in range(1, self.log + 1)] def get(self, p): p += self.size [self._push(p >> i) for i in reversed(range(1, self.log + 1))] return self.d[p] __setitem__ = set def __getitem__(self, k): if isinstance(k, slice): l = k.start if k.start is not None else 0 r = k.stop if k.stop is not None else self._n - 1 if l < 0: l += self._n if r < 0: r += self._n if l == 0 and r == self._n - 1: return self.all_prod() return self.prod(l, r + 1) return self.get(k) def prod(self, l, r): if l == r: return self.e l += self.size r += self.size for i in reversed(range(1, self.log + 1)): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) sml, smr = self.e, self.e while l < r: if l & 1: sml = self.op(sml, self.d[l]) l += 1 if r & 1: r -= 1 smr = self.op(self.d[r], smr) l >>= 1 r >>= 1 return self.op(sml, smr) def all_prod(self): return self.d[1] def apply_point(self, p, f): p += self.size [self._push(p >> i) for i in reversed(range(1, self.log + 1))] self.d[p] = self.mapping(f, self.d[p]) [self._update(p >> i) for i in range(1, self.log + 1)] def apply(self, l, r, f): if l == r: return l += self.size r += self.size for i in reversed(range(1, self.log + 1)): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) l2, r2 = l, r while l < r: if l & 1: self._all_apply(l, f) l += 1 if r & 1: r -= 1 self._all_apply(r, f) l >>= 1 r >>= 1 l, r = l2, r2 for i in range(1, self.log + 1): if ((l >> i) << i) != l: self._update(l >> i) if ((r >> i) << i) != r: self._update((r - 1) >> i) def _update(self, k): self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1]) def _all_apply(self, k, f): self.d[k] = self.mapping(f, self.d[k]) if k < self.size: self.lz[k] = self.composition(f, self.lz[k]) def _push(self, k): self._all_apply(2 * k, self.lz[k]) self._all_apply(2 * k + 1, self.lz[k]) self.lz[k] = self.id INF = 10**16 def sum2(x, y): return (x[0] + y[0], x[1] + y[1]) def add(f, x): return f + x def add2(f, x): return (x[0] + f * x[1], x[1]) def add_comp(f, g): return f + g def update(f, x): return f if f < INF else x def update_min(f, x): return min(f, x) def update2(f, x): return (f * x[1], x[1]) if f < INF else x def update_comp(f, g): return f if f < INF else g class Discrete: def __init__(self, a=[]): self.nums = set(a) self.d = {} self.n = 0 def add(self, num): self.nums.add(num) def distinct(self): self.n = len(self.nums) self.nums = list(self.nums) self.nums.sort() self.d = dict(zip(self.nums, range(self.n))) def __call__(self, num): return self.d[num] def __enter__(self): return self def __exit__(self, exc_type, exc_val, exc_tb): self.distinct() ic = Debug(1).get_ic() n, _ = MII() xs = LII(1) lrs = [LII(1) for _ in range(II())] with Discrete() as dc: for x in xs: dc.add(x) for l, r in lrs: dc.add(l) dc.add(r) dc.add(r + 1) st = SegmentTree(dc.n + 1) for i, (l, r) in enumerate(lrs, 1): st.apply(dc(l), dc(r) + 1, i) for x in xs: print(st[dc(x)] or -1)