AtCoder Beginner Contest 260 の A 〜 E を解く

def resolve():
  from collections import Counter

  # {<文字>: 含まれる個数} という形式になるように集計する。
  S = Counter(list(input()))

  # k : 文字
  # v : その文字が与えられた文字列に含まれている個数
  for k, v in S.items():
    # 与えられた文字列に k が 1 個だけ含まれているとき、それが答え
    if v == 1:
      print(k)
      return
  # 該当する文字が見つからなかった場合、-1 を出力する。
  print(-1)

resolve()

def resolve():
  N, X, Y, Z = map(int, input().split(" "))
  A = [int(x) for x in input().split(" ")]
  B = [int(x) for x in input().split(" ")]

  # 数学・英語・数学＋英語それぞれの点数が大きい順に並べる。
  # 点数が同じだった場合、受験番号が小さい方が前に来るように、受験番号を負の値にする。
  MATH = sorted([(a, -(i+1)) for i, a in enumerate(A)], reverse=True)
  ENGLISH = sorted([(b, -(i+1)) for i, b in enumerate(B)], reverse=True)
  SUM = sorted([(A[i]+B[i], -(i+1)) for i in range(N)], reverse=True)

  # fixed: 合格した人のインデックスの集合
  fixed = set()

  # 数学の点数が高い方から X 人合格させる。
  for _, i in MATH:
    if len(fixed) == X: break
    fixed.add(i)

  # 英語の点数が高い方から Y 人合格させる。
  # 既に X 人合格しているので、この処理が終わった時点で X + Y 人合格していることになる。
  for _, i in ENGLISH:
    if len(fixed) == X+Y: break
    fixed.add(i)

  # 数学 + 英語の点数が高い方から Z 人合格させる。
  # 既に X + Y 人合格しているので、この処理が終わった時点で X + Y + Z 人合格していることになる。
  for _, i in SUM:
    if len(fixed) == X+Y+Z: break
    fixed.add(i)

  # ソートする時にインデックスを負の値にしたので再度反転させる。
  ans = sorted([-i for i in list(fixed)])

  print(*ans, sep="\n")

resolve()

def resolve():
  N, X, Y = map(int, input().split(" "))
  # dp[n][c]: レベル N の赤い宝石 1 個からはじめた時に、
  # レベル n の c (c == 0: 赤、c == 1: 青) 色の宝石の最大の個数。
  dp = [[0, 0] for _ in range(N+1)]

  # 初期値。レベル N の赤色の宝石を 1 個持っている状態から始まる。
  dp[N][0] = 1
  for n in range(N, 1, -1):
    # 赤色の宝石に操作を行うときの遷移
    dp[n-1][0] += dp[n][0]
    dp[n][1] += X*dp[n][0]

    # 青色の宝石に操作を行うときの遷移
    dp[n-1][0] += dp[n][1]
    dp[n-1][1] += Y*dp[n][1]

  # 最終的にレベル 1 の青色の宝石を何個作ることができるかを出力する。
  print(dp[1][1])

resolve()

# SortedMultiset: tatyam さんの作った SortedMultiset を利用させていただいています。
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedMultiset(Generic[T]):
  BUCKET_RATIO = 50
  REBUILD_RATIO = 170

  def _build(self, a=None) -> None:
    "Evenly divide `a` into buckets."
    if a is None: a = list(self)
    size = self.size = len(a)
    bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
    self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
  
  def __init__(self, a: Iterable[T] = []) -> None:
    "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
    a = list(a)
    if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
        a = sorted(a)
    self._build(a)

  def __iter__(self) -> Iterator[T]:
    for i in self.a:
      for j in i: yield j

  def __reversed__(self) -> Iterator[T]:
    for i in reversed(self.a):
      for j in reversed(i): yield j
  
  def __len__(self) -> int:
    return self.size
  
  def __repr__(self) -> str:
    return "SortedMultiset" + str(self.a)
  
  def __str__(self) -> str:
    s = str(list(self))
    return "{" + s[1 : len(s) - 1] + "}"

  def _find_bucket(self, x: T) -> List[T]:
    "Find the bucket which should contain x. self must not be empty."
    for a in self.a:
      if x <= a[-1]: return a
    return a

  def __contains__(self, x: T) -> bool:
    if self.size == 0: return False
    a = self._find_bucket(x)
    i = bisect_left(a, x)
    return i != len(a) and a[i] == x

  def deck_count(self, x: T) -> int:
    "deck_count the number of x."
    return self.index_right(x) - self.index(x)

  def add(self, x: T) -> None:
    "Add an element. / O(√N)"
    if self.size == 0:
      self.a = [[x]]
      self.size = 1
      return
    a = self._find_bucket(x)
    insort(a, x)
    self.size += 1
    if len(a) > len(self.a) * self.REBUILD_RATIO:
      self._build()

  def discard(self, x: T) -> bool:
    "Remove an element and return True if removed. / O(√N)"
    if self.size == 0: return False
    a = self._find_bucket(x)
    i = bisect_left(a, x)
    if i == len(a) or a[i] != x: return False
    a.pop(i)
    self.size -= 1
    if len(a) == 0: self._build()
    return True

  def lt(self, x: T) -> Union[T, None]:
    "Find the largest element < x, or None if it doesn't exist."
    for a in reversed(self.a):
      if a[0] < x:
        return a[bisect_left(a, x) - 1]

  def le(self, x: T) -> Union[T, None]:
    "Find the largest element <= x, or None if it doesn't exist."
    for a in reversed(self.a):
      if a[0] <= x:
        return a[bisect_right(a, x) - 1]

  def gt(self, x: T) -> Union[T, None]:
    "Find the smallest element > x, or None if it doesn't exist."
    for a in self.a:
      if a[-1] > x:
        return a[bisect_right(a, x)]

  def ge(self, x: T) -> Union[T, None]:
    "Find the smallest element >= x, or None if it doesn't exist."
    for a in self.a:
      if a[-1] >= x:
        return a[bisect_left(a, x)]

  def __getitem__(self, x: int) -> T:
    "Return the x-th element, or IndexError if it doesn't exist."
    if x < 0: x += self.size
    if x < 0: raise IndexError
    for a in self.a:
      if x < len(a): return a[x]
      x -= len(a)
    raise IndexError

  def index(self, x: T) -> int:
    "Count the number of elements < x."
    ans = 0
    for a in self.a:
      if a[-1] >= x:
        return ans + bisect_left(a, x)
      ans += len(a)
    return ans

  def index_right(self, x: T) -> int:
    "Count the number of elements <= x."
    ans = 0
    for a in self.a:
      if a[-1] > x:
        return ans + bisect_right(a, x)
      ans += len(a)
    return ans

def resolve():
  N, K = map(int, input().split(" "))

  # 後々カード同士の結合関係を使う処理を入れるので、カードに書かれた番号を 0-index に対応させるために -1 している。
  P = [int(x)-1 for x in input().split(" ")]

  # ans[i]: i 番目のカードが何ターン目に食べられるか
  ans = [-1]*N

  # deck_tops: 場に見えているカード
  deck_tops = SortedMultiset([])

  # parents[i]: i と書かれたカードの下に書かれたカードに書かれている数字
  parents = [-1]*N

  # deck_count[i]: 場に見えているカードに書かれた数字が i だった時、そのカードが乗っている山に何枚のカードが含まれるのか
  deck_count = [1]*N
  for turn in range(1, N+1):
    # p: 新しく引いたカードに書かれた番号
    p = P[turn-1]

    # 場に出ているカードの内、p 以上のカードの番号
    ele = deck_tops.gt(p)

    # 重ねる対象となるカードが存在する場合、
    # その山のトップと新しく引いたカードの関連付けを行なった上で deck_tops からその山のトップを除去する。
    # (直後に新しく引いたカードを山の一番上として登録するので山自体が消えるわけではない。)
    if ele is not None:
      deck_count[p] = deck_count[ele] + 1
      parents[p] = ele
      deck_tops.discard(ele)

    deck_tops.add(p)

    # 山を食べる動作
    if deck_count[p] >= K:
      deck_tops.discard(p)
      while p >= 0:
        ans[p] = turn
        p = parents[p]

  print(*ans, sep="\n")

resolve()

def resolve():
  from collections import defaultdict
  N, M = map(int, input().split(" "))
  indexes = [[] for _ in range(M)]

  # 尺取法をする時に扱いやすいようにデータを持っておく。
  # indexes[X]: 整数 X を持っている整数の組の番号
  for i in range(N):
    a, b = [int(x)-1 for x in input().split(" ")]
    indexes[a].append(i)
    indexes[b].append(i)

  # imos[k]: 長さ k の
  imos = [0]*(M+1)

  # count[i]: 現在、整数の組の番号 i がもつ数字が区間 [L, R) に何個含まれているか
  count = [0]*M

  # includes: Ai, Bi どちらかが [L, R) に含まれる整数の組の番号を管理するための set
  includes = set()
  r = 0
  for l in range(M):
    # [l, r) が良い数列になるか、r をそれ以上右に動かせなくなるまで r を移動させる
    while r < M and len(includes) < N:
      for i in indexes[r]:
        count[i] += 1
        includes.add(i)
      r += 1

    # f(k) (k: r-l ~ M-l) の結果全てに 1 を足す操作
    # いもす法なので、操作する区間の先頭と末尾に値を差し引きするだけ
    if len(includes) == N:
      imos[r-l] += 1
      if M-l+1 <= M: imos[M-l+1] -= 1

    # 左を動かすタイミングで整数の組の番号 i がもつ数字が区間 [l, r) に何個含まれているか？を減らす
    for i in indexes[l]:
      count[i] -= 1
      # count[i] が 1 => 0 に変化したということは、
      # 整数の組 i が区間 [l, r) に含まれなくなったということなので includes から除く
      if count[i] == 0:
        includes.remove(i)

  # いもす法の全体シミュレートを実行する。
  for i in range(1, M+1):
    imos[i] += imos[i-1]
  print(*(imos[1:]))

resolve()