#857898 (TypeScript) No.1074 増殖

提出ソース

結果

問題	No.1074 増殖
ユーザー	草苺奶昔
提出日時	2023-04-08 14:52:05
言語	TypeScript (5.4.3)
結果	CE (最新) AC (最初)
実行時間	-
コード長	15,256 bytes
コンパイル時間	5,598 ms
コンパイル使用メモリ	148,088 KB
最終ジャッジ日時	2024-04-27 04:36:59
合計ジャッジ時間	6,567 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ

main.ts(531,23): error TS2307: Cannot find module 'fs' or its corresponding type declarations.
main.ts(532,27): error TS2307: Cannot find module 'path' or its corresponding type declarations.
main.ts(537,38): error TS2304: Cannot find name '__dirname'.
main.ts(539,30): error TS2580: Cannot find name 'process'. Do you need to install type definitions for node? Try `npm i --save-dev @types/node`.

ソースコード

raw source code

const INF = 2e15

/**
 * A fast SortedList with O(sqrt(n)) insertion and deletion.
 *
 * @_see {@link https://github.com/981377660LMT/algorithm-study/blob/master/22_%E4%B8%93%E9%A2%98/%E7%A6%BB%E7%BA%BF%E6%9F%A5%E8%AF%A2/%E6%A0%B9%E5%8F%B7%E5%88%86%E6%B2%BB/SortedList/SortedList.ts}
 * @_see {@link https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py}
 * @_see {@link https://qiita.com/tatyam/items/492c70ac4c955c055602}
 * @_see {@link https://speakerdeck.com/tatyam_prime/python-dezui-qiang-falseping-heng-er-fen-tan-suo-mu-wozuo-ru}
 */
class SortedList<T = number> {
  /** Optimized for 1e5 elements in javascript. Do not change it. */
  protected static readonly _BLOCK_RATIO = 50
  protected static readonly _REBUILD_RATIO = 170

  protected readonly _compareFn: (a: T, b: T) => number
  protected _size: number
  protected _blocks: T[][]

  constructor()
  constructor(iterable: Iterable<T>)
  constructor(compareFn: (a: T, b: T) => number)
  constructor(iterable: Iterable<T>, compareFn: (a: T, b: T) => number)
  constructor(compareFn: (a: T, b: T) => number, iterable: Iterable<T>)
  constructor(
    arg1?: Iterable<T> | ((a: T, b: T) => number),
    arg2?: Iterable<T> | ((a: T, b: T) => number)
  ) {
    let defaultCompareFn = (a: T, b: T) => (a as unknown as number) - (b as unknown as number)
    let defaultData: T[] = []
    if (arg1 !== void 0) {
      if (typeof arg1 === 'function') {
        defaultCompareFn = arg1
      } else {
        defaultData = [...arg1]
      }
    }
    if (arg2 !== void 0) {
      if (typeof arg2 === 'function') {
        defaultCompareFn = arg2
      } else {
        defaultData = [...arg2]
      }
    }

    this._compareFn = defaultCompareFn
    defaultData.sort(defaultCompareFn)
    this._blocks = this._initBlocks(defaultData)
    this._size = defaultData.length
  }

  add(value: T): void {
    if (!this._size) {
      this._blocks = [[value]]
      this._size = 1
      return
    }

    const blockIndex = this._findBlockIndex(value)
    if (blockIndex === -1) {
      this._blocks[this._blocks.length - 1].push(value)
      this._size++
      if (
        this._blocks[this._blocks.length - 1].length >
        this._blocks.length * SortedList._REBUILD_RATIO
      ) {
        this._rebuild()
      }
      return
    }

    const block = this._blocks[blockIndex]
    const pos = this._bisectRight(block, value)
    block.splice(pos, 0, value)
    this._size += 1
    if (block.length > this._blocks.length * SortedList._REBUILD_RATIO) {
      this._rebuild()
    }
  }

  /** 注意内部使用 `===` 来比较两个对象是否相等 */
  has(value: T): boolean {
    if (!this._size) return false
    const blockIndex = this._findBlockIndex(value)
    if (blockIndex === void 0) return false
    const block = this._blocks[blockIndex]
    const pos = this._bisectLeft(block, value)
    return pos < block.length && value === block[pos]
  }

  /** 注意内部使用 `===` 来比较两个对象是否相等 */
  discard(value: T): boolean {
    if (!this._size) return false
    const blockIndex = this._findBlockIndex(value)
    if (blockIndex === -1) return false
    const block = this._blocks[blockIndex]
    const pos = this._bisectLeft(block, value)
    if (pos === block.length || block[pos] !== value) {
      return false
    }
    block.splice(pos, 1)
    this._size -= 1
    if (!block.length) {
      this._blocks.splice(blockIndex, 1) // !Splice When Empty, Do Not Rebuild
    }
    return true
  }

  pop(index = -1): T | undefined {
    if (index < 0) index += this._size
    if (index < 0 || index >= this._size) {
      return void 0
    }
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (index < block.length) {
        const res = block[index]
        block.splice(index, 1)
        this._size -= 1
        if (!block.length) {
          this._blocks.splice(i, 1) // !Splice When Empty, Do Not Rebuild
        }
        return res
      }
      index -= block.length
    }
    return void 0
  }

  /**
   * 删除区间 [start, end) 内的元素.
   */
  erase(start: number, end: number): void {
    if (start < 0) start = 0
    if (end > this._size) end = this._size
    if (start >= end) return

    let [bid, startPos] = this._moveTo(start)
    let deleteCount = end - start
    for (; bid < this._blocks.length && deleteCount > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + deleteCount)
      const curDeleteCount = endPos - startPos
      if (curDeleteCount === block.length) {
        this._blocks.splice(bid, 1)
        bid--
      } else {
        block.splice(startPos, curDeleteCount)
      }
      deleteCount -= curDeleteCount
      this._size -= curDeleteCount
      startPos = 0
    }
  }

  at(index: number): T | undefined {
    if (index < 0) index += this._size
    if (index < 0 || index >= this._size) {
      return void 0
    }
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (index < block.length) {
        return block[index]
      }
      index -= block.length
    }
    return void 0
  }

  lower(value: T): T | undefined {
    for (let i = this._blocks.length - 1; ~i; i--) {
      const block = this._blocks[i]
      if (this._compareFn(block[0], value) < 0) {
        const pos = this._bisectLeft(block, value)
        return block[pos - 1]
      }
    }
    return void 0
  }

  higher(value: T): T | undefined {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(block[block.length - 1], value) > 0) {
        const pos = this._bisectRight(block, value)
        return block[pos]
      }
    }
    return void 0
  }

  floor(value: T): T | undefined {
    for (let i = this._blocks.length - 1; ~i; i--) {
      const block = this._blocks[i]
      if (this._compareFn(block[0], value) <= 0) {
        const pos = this._bisectRight(block, value)
        return block[pos - 1]
      }
    }
    return void 0
  }

  ceiling(value: T): T | undefined {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(block[block.length - 1], value) >= 0) {
        const pos = this._bisectLeft(block, value)
        return block[pos]
      }
    }
    return void 0
  }

  /**
   * Count the number of elements < value or
   * returns the index of the first element >= value.
   */
  bisectLeft(value: T): number {
    let res = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(value, block[block.length - 1]) <= 0) {
        return res + this._bisectLeft(block, value)
      }
      res += block.length
    }
    return res
  }

  /**
   * Count the number of elements <= value or
   * returns the index of the first element > value.
   */
  bisectRight(value: T): number {
    let res = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(value, block[block.length - 1]) < 0) {
        return res + this._bisectRight(block, value)
      }
      res += block.length
    }
    return res
  }

  slice(start: number, end: number): T[] {
    if (start < 0) start = 0
    if (end > this._size) end = this._size
    if (start >= end) return []
    let count = end - start
    const res: T[] = Array(count).fill(0)
    let [bid, startPos] = this._moveTo(start)
    let ptr = 0
    for (; bid < this._blocks.length && count > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + count)
      const curCount = endPos - startPos
      for (let j = startPos; j < endPos; j++) {
        res[ptr++] = block[j]
      }
      count -= curCount
      startPos = 0
    }
    return res
  }

  clear(): void {
    this._blocks = []
    this._size = 0
  }

  toString(): string {
    return `SortedList[${[...this].join(', ')}]`
  }

  /**
   * 返回一个迭代器，用于遍历区间 [start, end) 内的元素.
   */
  *islice(start: number, end: number): IterableIterator<T> {
    if (start < 0) start = 0
    if (end > this._size) end = this._size
    if (start >= end) return
    let count = end - start
    let [bid, startPos] = this._moveTo(start)
    for (; bid < this._blocks.length && count > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + count)
      const curCount = endPos - startPos
      for (let j = startPos; j < endPos; j++) {
        yield block[j]
      }
      count -= curCount
      startPos = 0
    }
  }

  /**
   * 返回一个迭代器，用于遍历范围在 `[min, max] 闭区间`内的元素.
   */
  *irange(min: T, max: T): IterableIterator<T> {
    const bi = this._findBlockIndex(min)
    for (let i = bi; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        const x = block[j]
        if (this._compareFn(x, max) > 0) {
          return
        }
        if (this._compareFn(x, min) >= 0) {
          yield x
        }
      }
    }
  }

  enumerate(start: number, end: number, f: (value: T) => void, erase = false): void {
    let [bid, startPos] = this._moveTo(start)
    let count = end - start

    for (; bid < this._blocks.length && count > 0; bid++) {
      const block = this._blocks[bid]
      const endPos = Math.min(block.length, startPos + count)
      for (let j = startPos; j < endPos; j++) {
        f(block[j])
      }

      const curDeleteCount = endPos - startPos
      if (erase) {
        if (curDeleteCount === block.length) {
          this._blocks.splice(bid, 1)
          bid--
        } else {
          block.splice(startPos, curDeleteCount)
        }
        this._size -= curDeleteCount
      }

      count -= curDeleteCount
      startPos = 0
    }
  }

  forEach(callbackfn: (value: T, index: number) => void): void {
    let pos = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        callbackfn(block[j], pos++)
      }
    }
  }

  *entries(): IterableIterator<[number, T]> {
    let pos = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        yield [pos++, block[j]]
      }
    }
  }

  *[Symbol.iterator](): Iterator<T> {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      for (let j = 0; j < block.length; j++) {
        yield block[j]
      }
    }
  }

  // Find the block which should contain x. Block must not be empty.
  private _findBlockIndex(x: T): number {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (this._compareFn(x, block[block.length - 1]) <= 0) {
        return i
      }
    }
    return -1
  }

  private _rebuild(): void {
    if (!this._size) {
      return
    }
    const bCount = Math.ceil(Math.sqrt(this._size / SortedList._BLOCK_RATIO))
    const bSize = ~~((this._size + bCount - 1) / bCount) // ceil
    const newB: T[][] = Array(bCount).fill(0)
    for (let i = 0; i < bCount; i++) {
      newB[i] = []
    }
    let ptr = 0
    for (let i = 0; i < this._blocks.length; i++) {
      const b = this._blocks[i]
      for (let j = 0; j < b.length; j++) {
        newB[~~(ptr / bSize)].push(b[j])
        ptr++
      }
    }
    this._blocks = newB
  }

  // eslint-disable-next-line class-methods-use-this
  private _initBlocks(sorted: T[]): T[][] {
    const bCount = Math.ceil(Math.sqrt(sorted.length / SortedList._BLOCK_RATIO))
    const bSize = ~~((sorted.length + bCount - 1) / bCount) // ceil
    const newB: T[][] = Array(bCount).fill(0)
    for (let i = 0; i < bCount; i++) {
      newB[i] = []
    }
    for (let i = 0; i < bCount; i++) {
      for (let j = i * bSize; j < Math.min((i + 1) * bSize, sorted.length); j++) {
        newB[i].push(sorted[j])
      }
    }
    return newB
  }

  private _bisectLeft(nums: T[], value: T): number {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
      const mid = (left + right) >> 1
      if (this._compareFn(value, nums[mid]) <= 0) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    return left
  }

  private _bisectRight(nums: T[], value: T): number {
    let left = 0
    let right = nums.length - 1
    while (left <= right) {
      const mid = (left + right) >> 1
      if (this._compareFn(value, nums[mid]) < 0) {
        right = mid - 1
      } else {
        left = mid + 1
      }
    }
    return left
  }

  private _moveTo(index: number): [blockId: number, startPos: number] {
    for (let i = 0; i < this._blocks.length; i++) {
      const block = this._blocks[i]
      if (index < block.length) {
        return [i, index]
      }
      index -= block.length
    }
    return [this._blocks.length, 0]
  }

  get length(): number {
    return this._size
  }
}

/**
 * !`包含原点的`矩形合并/矩形面积并.
 */
class UnionRectangleRange {
  private readonly _ur = new UnionRectangle()
  private readonly _ul = new UnionRectangle()
  private readonly _dr = new UnionRectangle()
  private readonly _dl = new UnionRectangle()

  /**
   * Add [x1, x2] * [y1, y2].
   * x1 <= 0 <= x2.
   * y1 <= 0 <= y2.
   */
  add(x1: number, x2: number, y1: number, y2: number): void {
    this._ur.add(x2, y2)
    this._ul.add(-x1, y2)
    this._dr.add(x2, -y1)
    this._dl.add(-x1, -y1)
  }

  query(): number {
    return this._ur.sum + this._ul.sum + this._dr.sum + this._dl.sum
  }
}

class UnionRectangle {
  sum = 0
  private readonly _sl = new SortedList(
    [
      [0, INF],
      [INF, 0]
    ],
    (a, b) => a[0] - b[0]
  )

  /**
   * Add [0, x] * [0, y].
   * x >= 0.
   * y >= 0.
   */
  add(x: number, y: number): void {
    let pos = this._sl.bisectLeft([x, -INF])
    const item = this._sl.at(pos)!
    if (item[1] >= y) return
    const nextY = item[1]
    pos--
    let pre = this._sl.at(pos)!
    while (pre[1] <= y) {
      const x1 = pre[0]
      const y1 = pre[1]
      this._sl.pop(pos)
      pos--
      pre = this._sl.at(pos)!
      this.sum -= (x1 - pre[0]) * (y1 - nextY)
    }
    this.sum += (x - this._sl.at(pos)![0]) * (y - nextY)
    pos = this._sl.bisectLeft([x, -INF])
    if (this._sl.at(pos)![0] === x) this._sl.pop(pos)
    this._sl.add([x, y])
  }

  query(): number {
    return this.sum
  }
}
  import * as fs from 'fs'
  import { resolve } from 'path'

  function useInput(path?: string) {
    let data: string
    if (path) {
      data = fs.readFileSync(resolve(__dirname, path), 'utf8')
    } else {
      data = fs.readFileSync(process.stdin.fd, 'utf8')
    }

    const lines = data.split(/\r\n|\r|\n/)
    let lineId = 0
    const input = (): string => lines[lineId++]

    return {
      input
    }
  }

  const { input } = useInput()
  const n = Number(input())
  const R = new UnionRectangleRange()
  let pre = 0
  for (let i = 0; i < n; i++) {
    const [x1,y1, x2, y2] = input().split(' ').map(Number)
    R.add(x1, x2, y1, y2)
    const cur = R.query()
    console.log(cur - pre)
    pre = cur
  }

yukicoder

結果

コンパイルメッセージ

ソースコード