結果
| 問題 |
No.1074 増殖
|
| コンテスト | |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-04-08 14:52:05 |
| 言語 | TypeScript (5.7.2) |
| 結果 |
AC
|
| 実行時間 | 935 ms / 2,000 ms |
| コード長 | 15,256 bytes |
| コンパイル時間 | 8,591 ms |
| コンパイル使用メモリ | 231,208 KB |
| 実行使用メモリ | 60,544 KB |
| 最終ジャッジ日時 | 2024-12-31 16:49:21 |
| 合計ジャッジ時間 | 17,119 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 |
ソースコード
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
}