結果

問題 No.2796 Small Matryoshka
ユーザー dp_ijkdp_ijk
提出日時 2024-06-28 23:05:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 995 ms / 2,000 ms
コード長 4,779 bytes
コンパイル時間 142 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 100,820 KB
最終ジャッジ日時 2024-06-28 23:05:25
合計ジャッジ時間 10,267 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
68,748 KB
testcase_01 AC 63 ms
68,868 KB
testcase_02 AC 62 ms
68,628 KB
testcase_03 AC 80 ms
68,124 KB
testcase_04 AC 65 ms
69,036 KB
testcase_05 AC 171 ms
81,784 KB
testcase_06 AC 577 ms
96,144 KB
testcase_07 AC 68 ms
69,620 KB
testcase_08 AC 532 ms
91,872 KB
testcase_09 AC 995 ms
100,820 KB
testcase_10 AC 693 ms
100,004 KB
testcase_11 AC 802 ms
100,428 KB
testcase_12 AC 440 ms
91,452 KB
testcase_13 AC 209 ms
80,880 KB
testcase_14 AC 396 ms
88,908 KB
testcase_15 AC 215 ms
81,904 KB
testcase_16 AC 278 ms
83,808 KB
testcase_17 AC 643 ms
95,360 KB
testcase_18 AC 765 ms
98,376 KB
testcase_19 AC 296 ms
83,916 KB
testcase_20 AC 393 ms
86,044 KB
testcase_21 AC 649 ms
96,408 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right
from typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, Optional
T = TypeVar('T')

class SortedMultiset(Generic[T]):
   BUCKET_RATIO = 16
   SPLIT_RATIO = 24

   def __init__(self, a: Iterable[T] = []) -> None:
      "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
      a = list(a)
      n = self.size = len(a)
      if any(a[i] > a[i + 1] for i in range(n - 1)):
         a.sort()
      num_bucket = int(math.ceil(math.sqrt(n / self.BUCKET_RATIO)))
      self.a = [a[n * i // num_bucket : n * (i + 1) // num_bucket] for i in range(num_bucket)]

   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 __eq__(self, other) -> bool:
      return list(self) == list(other)

   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 _position(self, x: T) -> Tuple[List[T], int, int]:
      "return the bucket, index of the bucket and position in which x should be. self must not be empty."
      for i, a in enumerate(self.a):
         if x <= a[-1]: break
      return (a, i, bisect_left(a, x))

   def __contains__(self, x: T) -> bool:
      if self.size == 0: return False
      a, _, i = self._position(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, b, i = self._position(x)
      a.insert(i, x)
      self.size += 1
      if len(a) > len(self.a) * self.SPLIT_RATIO:
         mid = len(a) >> 1
         self.a[b:b+1] = [a[:mid], a[mid:]]

   def _pop(self, a: List[T], b: int, i: int) -> T:
      ans = a.pop(i)
      self.size -= 1
      if not a: del self.a[b]
      return ans

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

   def lt(self, x: T) -> Optional[T]:
      "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) -> Optional[T]:
      "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) -> Optional[T]:
      "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) -> Optional[T]:
      "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, i: int) -> T:
      "Return the i-th element."
      if i < 0:
         for a in reversed(self.a):
            i += len(a)
            if i >= 0: return a[i]
      else:
         for a in self.a:
            if i < len(a): return a[i]
            i -= len(a)
      raise IndexError

   def pop(self, i: int = -1) -> T:
      "Pop and return the i-th element."
      if i < 0:
         for b, a in enumerate(reversed(self.a)):
            i += len(a)
            if i >= 0: return self._pop(a, ~b, i)
      else:
         for b, a in enumerate(self.a):
            if i < len(a): return self._pop(a, b, i)
            i -= 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

from bisect import bisect_left, bisect_right
N = int(input())
LR = [tuple(map(int, input().split())) for _ in range(N)]
LR.sort(key=lambda x: x[1], reverse=True)

Q = SortedMultiset()
while LR:
   l, r = LR.pop()
   j = Q.le(l)
   if j is None:
      Q.add(r)
   else:
      Q.discard(j)
      Q.add(r)

ans = len(Q) - 1
print(ans)
0