結果

問題 No.2650 [Cherry 6th Tune *] セイジャク
コンテスト
ユーザー katonyonko
提出日時 2024-02-23 22:15:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 833 ms / 2,500 ms
コード長 5,631 bytes
コンパイル時間 266 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 114,888 KB
最終ジャッジ日時 2024-09-29 07:00:55
合計ジャッジ時間 21,339 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import io
import sys
from collections import defaultdict, deque, Counter
from itertools import permutations, combinations, accumulate
from heapq import heappush, heappop
from bisect import bisect_right, bisect_left
from math import gcd
import math

_INPUT = """\
6
4 15
3 8 11 14
4
1 6
12 14
7 10
5 9
1 1000000000
500000000
1
499999999 500000001
"""

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 count(self, x: T) -> int:
      "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 input():
  return sys.stdin.readline()[:-1]

def solve(test):
  N,A=map(int, input().split())
  X=list(map(int, input().split()))
  X=sorted([(X[i],i) for i in range(N)])
  Y=[X[i][0] for i in range(N)]
  T=int(input())
  ans=[-1]*N
  query=[[] for _ in range(N+1)]
  ms=SortedMultiset()
  for t in range(T):
    L,R=map(int, input().split())
    R+=1
    query[bisect_left(Y,L)].append(t+1)
    query[bisect_left(Y,R)].append(-t-1)
  for i in range(N):
    for t in query[i]:
      if t>0:
        ms.add(t)
      else:
        ms.discard(-t)
    if ms.size>0:
      ans[X[i][1]]=ms[-1]
  for a in ans:
    print(a)

def random_input():
  from random import randint,shuffle
  N=randint(1,10)
  M=randint(1,N)
  A=list(range(1,M+1))+[randint(1,M) for _ in range(N-M)]
  shuffle(A)
  return (" ".join(map(str, [N,M]))+"\n"+" ".join(map(str, A))+"\n")*3

def simple_solve():
  return []

def main(test):
  if test==0:
    solve(0)
  elif test==1:
    sys.stdin = io.StringIO(_INPUT)
    case_no=int(input())
    for _ in range(case_no):
      solve(0)
  else:
    for i in range(1000):
      sys.stdin = io.StringIO(random_input())
      x=solve(1)
      y=simple_solve()
      if x!=y:
        print(i,x,y)
        print(*[line for line in sys.stdin],sep='')
        break

#0:提出用、1:与えられたテスト用、2:ストレステスト用
main(0)
0