結果
| 問題 | No.1074 増殖 |
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-10-14 13:20:06 |
| 言語 | TypeScript (5.4.3) |
| 結果 |
AC
|
| 実行時間 | 910 ms / 2,000 ms |
| コード長 | 22,073 bytes |
| コンパイル時間 | 7,187 ms |
| コンパイル使用メモリ | 261,072 KB |
| 実行使用メモリ | 62,048 KB |
| 最終ジャッジ日時 | 2023-10-14 13:20:27 |
| 合計ジャッジ時間 | 15,817 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 78 ms
42,432 KB |
| testcase_01 | AC | 80 ms
42,684 KB |
| testcase_02 | AC | 78 ms
42,588 KB |
| testcase_03 | AC | 77 ms
42,472 KB |
| testcase_04 | AC | 83 ms
42,532 KB |
| testcase_05 | AC | 81 ms
42,884 KB |
| testcase_06 | AC | 779 ms
60,248 KB |
| testcase_07 | AC | 750 ms
59,952 KB |
| testcase_08 | AC | 791 ms
61,384 KB |
| testcase_09 | AC | 821 ms
62,048 KB |
| testcase_10 | AC | 679 ms
59,956 KB |
| testcase_11 | AC | 746 ms
62,032 KB |
| testcase_12 | AC | 722 ms
60,960 KB |
| testcase_13 | AC | 910 ms
61,388 KB |
| testcase_14 | AC | 904 ms
61,480 KB |
ソースコード
const INF = 2e9
/**
* !`包含原点的`矩形合并/矩形面积并.
*/
class IncrementalRectangleUnionRange {
private readonly _ur = new IncrementalRectangleUnion()
private readonly _ul = new IncrementalRectangleUnion()
private readonly _dr = new IncrementalRectangleUnion()
private readonly _dl = new IncrementalRectangleUnion()
/**
* 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 IncrementalRectangleUnion {
sum = 0
private readonly _sl = new SortedListFast(
[
{ start: 0, end: INF },
{ start: INF, end: 0 }
],
(a, b) => a.start - b.start
)
/**
* Add [0, x] * [0, y].
* x >= 0.
* y >= 0.
*/
add(x: number, y: number): void {
let pos = this._sl.bisectLeft({ start: x, end: -INF })
const item = this._sl.at(pos)!
if (item.end >= y) return
const nextY = item.end
pos--
let pre = this._sl.at(pos)!
while (pre.end <= y) {
const x1 = pre.start
const y1 = pre.end
this._sl.pop(pos)
pos--
pre = this._sl.at(pos)!
this.sum -= (x1 - pre.start) * (y1 - nextY)
}
this.sum += (x - this._sl.at(pos)!.start) * (y - nextY)
pos = this._sl.bisectLeft({ start: x, end: -INF })
if (this._sl.at(pos)!.start === x) this._sl.pop(pos)
this._sl.add({ start: x, end: y })
}
query(): number {
return this.sum
}
}
// API.
interface ISortedList<V> {
add(value: V): void
has(value: V, equals?: (a: V, b: V) => boolean): boolean
discard(value: V, equals?: (a: V, b: V) => boolean): boolean
pop(index?: number): V | undefined
at(index: number): V | undefined
erase(start?: number, end?: number): void
lower(value: V): V | undefined
higher(value: V): V | undefined
floor(value: V): V | undefined
ceiling(value: V): V | undefined
bisectLeft(value: V): number
bisectRight(value: V): number
count(value: V): number
slice(start?: number, end?: number): V[]
clear(): void
update(...values: V[]): void
merge(other: ISortedList<V>): void
toString(): string
forEach(callbackfn: (value: V, index: number) => void | boolean, reverse?: boolean): void
enumerate(start: number, end: number, f: (value: V) => void, erase?: boolean): void
iSlice(start: number, end: number, reverse?: boolean): IterableIterator<V>
iRange(min: V, max: V, reverse?: boolean): IterableIterator<V>
entries(): IterableIterator<[number, V]>
[Symbol.iterator](): IterableIterator<V>
iteratorAt(index: number): ISortedListIterator<V>
lowerBound(value: V): ISortedListIterator<V>
upperBound(value: V): ISortedListIterator<V>
readonly length: number
readonly min: V | undefined
readonly max: V | undefined
}
interface ISortedListIterator<V> {
hasNext(): boolean
next(): V | undefined
hasPrev(): boolean
prev(): V | undefined
remove(): void
readonly value: V | undefined
}
/**
* 使用分块+树状数组维护的有序序列.
* !如果数组较短(<2000),直接使用`bisectInsort`维护即可.
*/
class SortedListFast<V = number> {
static setLoadFactor(load = 500): void {
this._LOAD = load
}
/**
* 负载因子，用于控制每个块的长度.
* 长度为`1e5`的数组, 负载因子取`500`左右性能较好.
*/
protected static _LOAD = 500
private static _isPrimitive(
o: unknown
): o is number | string | boolean | symbol | bigint | null | undefined {
return o === null || (typeof o !== 'object' && typeof o !== 'function')
}
protected _compareFn!: (a: V, b: V) => number
protected _len!: number
/**
* 各个块.
*/
protected _blocks!: V[][]
/**
* 各个块的最小值.
*/
protected _mins!: V[]
/**
* 树状数组维护各个块长度的前缀和，便于根据索引定位到对应的元素.
*/
protected _tree!: number[]
protected _shouldRebuildTree!: boolean
constructor()
constructor(iterable: Iterable<V>)
constructor(compareFn: (a: V, b: V) => number)
constructor(iterable: Iterable<V>, compareFn: (a: V, b: V) => number)
constructor(compareFn: (a: V, b: V) => number, iterable: Iterable<V>)
constructor(
arg1?: Iterable<V> | ((a: V, b: V) => number),
arg2?: Iterable<V> | ((a: V, b: V) => number)
) {
let defaultCompareFn = (a: V, b: V) => (a as unknown as number) - (b as unknown as number)
let defaultData: V[] = []
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._build(defaultData, defaultCompareFn)
}
add(value: V): this {
const { _blocks, _mins } = this
this._len++
if (!_blocks.length) {
_blocks.push([value])
_mins.push(value)
this._shouldRebuildTree = true
return this
}
const load = SortedListFast._LOAD
const pair = this._locRight(value)
const pos = pair[0]
const index = pair[1]
this._updateTree(pos, 1)
const block = _blocks[pos]
block.splice(index, 0, value)
_mins[pos] = block[0]
// !-> [x]*load + [x]*(block.length - load)
if (load + load < block.length) {
_blocks.splice(pos + 1, 0, block.slice(load))
_mins.splice(pos + 1, 0, block[load])
block.splice(load)
this._shouldRebuildTree = true
}
return this
}
update(...values: V[]): this {
const n = values.length
if (n < this._len << 2) {
for (let i = 0; i < n; i++) this.add(values[i])
return this
}
const data = Array(this._len + n)
let ptr = 0
this.forEach(v => {
data[ptr++] = v
})
for (let i = 0; i < n; i++) data[ptr++] = values[i]
this._build(data, this._compareFn)
return this
}
merge(other: SortedListFast<V>): this {
const n = other.length
if (n < this._len << 2) {
other.forEach(v => {
this.add(v)
})
return this
}
const data = Array(this._len + n)
let ptr = 0
this.forEach(v => {
data[ptr++] = v
})
other.forEach(v => {
data[ptr++] = v
})
this._build(data, this._compareFn)
return this
}
has(value: V, equals?: (a: V, b: V) => boolean): boolean {
if (!equals && !SortedListFast._isPrimitive(value)) {
throw new Error('equals must be provided when value is a non-primitive value')
}
const block = this._blocks
if (!block.length) return false
equals = equals || ((a: V, b: V) => a === b)
const pair = this._locLeft(value)
const pos = pair[0]
const index = pair[1]
return index < block[pos].length && equals(block[pos][index], value)
}
discard(value: V, equals?: (a: V, b: V) => boolean): boolean {
if (!equals && !SortedListFast._isPrimitive(value)) {
throw new Error('equals must be provided when value is a non-primitive value')
}
const block = this._blocks
if (!block.length) return false
equals = equals || ((a: V, b: V) => a === b)
const pair = this._locRight(value)
const pos = pair[0]
const index = pair[1]
if (index && equals(block[pos][index - 1], value)) {
this._delete(pos, index - 1)
return true
}
return false
}
pop(index = -1): V | undefined {
if (index < 0) index += this._len
if (index < 0 || index >= this._len) return void 0
const pair = this._findKth(index)
const pos = pair[0]
const index_ = pair[1]
const value = this._blocks[pos][index_]
this._delete(pos, index_)
return value
}
at(index: number): V | undefined {
if (index < 0) index += this._len
if (index < 0 || index >= this._len) return void 0
const pair = this._findKth(index)
const pos = pair[0]
const index_ = pair[1]
return this._blocks[pos][index_]
}
/**
* 删除区间 `[start, end)` 内的元素.
*/
erase(start = 0, end = this.length): void {
// eslint-disable-next-line @typescript-eslint/no-empty-function
this.enumerate(start, end, () => {}, true)
}
lower(value: V): V | undefined {
const pos = this.bisectLeft(value)
return pos ? this.at(pos - 1) : void 0
}
higher(value: V): V | undefined {
const pos = this.bisectRight(value)
return pos < this._len ? this.at(pos) : void 0
}
floor(value: V): V | undefined {
const pos = this.bisectRight(value)
return pos ? this.at(pos - 1) : void 0
}
ceiling(value: V): V | undefined {
const pos = this.bisectLeft(value)
return pos < this._len ? this.at(pos) : void 0
}
/**
* 返回第一个大于等于 `value` 的元素的索引/严格小于 `value` 的元素的个数.
*/
bisectLeft(value: V): number {
const pair = this._locLeft(value)
const pos = pair[0]
const index = pair[1]
return this._queryTree(pos) + index
}
/**
* 返回第一个严格大于 `value` 的元素的索引/小于等于 `value` 的元素的个数.
*/
bisectRight(value: V): number {
const pair = this._locRight(value)
const pos = pair[0]
const index = pair[1]
return this._queryTree(pos) + index
}
count(value: V): number {
return this.bisectRight(value) - this.bisectLeft(value)
}
slice(start = 0, end = this.length): V[] {
if (start < 0) start += this._len
if (start < 0) start = 0
if (end < 0) end += this._len
if (end > this._len) end = this._len
if (start >= end) return []
const res = Array(end - start)
let count = 0
this.enumerate(
start,
end,
value => {
res[count++] = value
},
false
)
return res
}
clear(): void {
this._len = 0
this._blocks = []
this._mins = []
this._tree = []
this._shouldRebuildTree = true
}
toString(): string {
const res = Array(this._len)
this.forEach((value, index) => {
res[index] = value
})
return `SortedList{${res.join(',')}}`
}
/**
* @param callbackfn 回调函数, 返回 `true` 时终止遍历.
* @param reverse 是否逆序遍历.
*/
forEach(callbackfn: (value: V, index: number) => void | boolean, reverse = false): void {
if (!reverse) {
let count = 0
for (let i = 0; i < this._blocks.length; i++) {
const block = this._blocks[i]
for (let j = 0; j < block.length; j++) {
if (callbackfn(block[j], count++)) return
}
}
return
}
let count = 0
for (let i = this._blocks.length - 1; ~i; i--) {
const block = this._blocks[i]
for (let j = block.length - 1; ~j; j--) {
if (callbackfn(block[j], count++)) return
}
}
}
enumerate(start: number, end: number, f: (value: V) => void, erase = false): void {
if (start < 0) start = 0
if (end > this._len) end = this._len
if (start >= end) return
const pair = this._findKth(start)
let pos = pair[0]
let startIndex = pair[1]
let count = end - start
for (; count && pos < this._blocks.length; pos++) {
const block = this._blocks[pos]
const endIndex = Math.min(block.length, startIndex + count)
for (let j = startIndex; j < endIndex; j++) f(block[j])
const deleted = endIndex - startIndex
if (erase) {
if (deleted === block.length) {
// !delete block
this._blocks.splice(pos, 1)
this._mins.splice(pos, 1)
this._shouldRebuildTree = true
pos--
} else {
// !delete [index, end)
for (let i = startIndex; i < endIndex; i++) this._updateTree(pos, -1)
block.splice(startIndex, deleted)
this._mins[pos] = block[0]
}
this._len -= deleted
}
count -= deleted
startIndex = 0
}
}
/**
* 返回一个迭代器，用于遍历区间 `[start, end)` 内的元素.
*/
*iSlice(start = 0, end = this.length, reverse = false): IterableIterator<V> {
if (start < 0) start += this._len
if (start < 0) start = 0
if (end < 0) end += this._len
if (end > this._len) end = this._len
if (start >= end) return
let count = end - start
if (reverse) {
let [pos, index] = this._findKth(end)
for (; count && ~pos; pos--, ~pos && (index = this._blocks[pos].length)) {
const block = this._blocks[pos]
const startPos = Math.max(0, index - count)
const curCount = index - startPos
for (let j = index - 1; j >= startPos; j--) yield block[j]
count -= curCount
}
} else {
let [pos, index] = this._findKth(start)
for (; count && pos < this._blocks.length; pos++) {
const block = this._blocks[pos]
const endPos = Math.min(block.length, index + count)
const curCount = endPos - index
for (let j = index; j < endPos; j++) yield block[j]
count -= curCount
index = 0
}
}
}
/**
* 返回一个迭代器，用于遍历范围在 `[min, max] 闭区间`内的元素.
*/
*iRange(min: V, max: V, reverse = false): IterableIterator<V> {
if (this._compareFn(min, max) > 0) return
if (reverse) {
let pos = this._locBlock(max)
for (let i = pos; ~i; i--) {
const block = this._blocks[i]
for (let j = block.length - 1; ~j; j--) {
const x = block[j]
if (this._compareFn(x, min) < 0) return
if (this._compareFn(x, max) <= 0) yield x
}
}
} else {
const pos = this._locBlock(min)
for (let i = pos; 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
}
}
}
}
*entries(): IterableIterator<[number, V]> {
let count = 0
for (let i = 0; i < this._blocks.length; i++) {
const block = this._blocks[i]
for (let j = 0; j < block.length; j++) {
yield [count++, block[j]]
}
}
}
*[Symbol.iterator](): IterableIterator<V> {
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]
}
}
}
iteratorAt(index: number): ISortedListIterator<V> {
if (index < 0) index += this._len
if (index < 0 || index >= this._len) throw new RangeError('Index out of range')
const pair = this._findKth(index)
return this._iteratorAt(pair[0], pair[1])
}
lowerBound(value: V): ISortedListIterator<V> {
const [pos, index] = this._locLeft(value)
return this._iteratorAt(pos, index)
}
upperBound(value: V): ISortedListIterator<V> {
const [pos, index] = this._locRight(value)
return this._iteratorAt(pos, index)
}
get length(): number {
return this._len
}
get min(): V | undefined {
if (!this._len) return void 0
return this._mins[0]
}
get max(): V | undefined {
if (!this._len) return void 0
const { _blocks } = this
const lastBlock = _blocks[_blocks.length - 1]
return lastBlock[lastBlock.length - 1]
}
protected _build(data: V[], compareFn: (a: V, b: V) => number): void {
data.sort(compareFn)
const n = data.length
const blocks = []
for (let i = 0; i < n; i += SortedListFast._LOAD) {
blocks.push(data.slice(i, i + SortedListFast._LOAD))
}
const mins = Array(blocks.length)
for (let i = 0; i < blocks.length; i++) {
const cur = blocks[i]
mins[i] = cur[0]
}
this._compareFn = compareFn
this._len = n
this._blocks = blocks
this._mins = mins
this._tree = []
this._shouldRebuildTree = true
}
protected _delete(pos: number, index: number): void {
const { _blocks, _mins } = this
// !delete element
this._len--
this._updateTree(pos, -1)
const block = _blocks[pos]
block.splice(index, 1)
if (block.length) {
_mins[pos] = block[0]
return
}
// !delete block
_blocks.splice(pos, 1)
_mins.splice(pos, 1)
this._shouldRebuildTree = true
}
protected _locLeft(value: V): [pos: number, index: number] {
if (!this._len) return [0, 0]
const { _blocks, _mins } = this
// find pos
let left = -1
let right = _blocks.length - 1
while (left + 1 < right) {
const mid = (left + right) >>> 1
if (this._compareFn(value, _mins[mid]) <= 0) {
right = mid
} else {
left = mid
}
}
if (right) {
const block = _blocks[right - 1]
if (this._compareFn(value, block[block.length - 1]) <= 0) {
right--
}
}
const pos = right
// find index
const cur = _blocks[pos]
left = -1
right = cur.length
while (left + 1 < right) {
const mid = (left + right) >>> 1
if (this._compareFn(value, cur[mid]) <= 0) {
right = mid
} else {
left = mid
}
}
return [pos, right]
}
protected _locRight(value: V): [pos: number, index: number] {
if (!this._len) return [0, 0]
const { _blocks, _mins } = this
// find pos
let left = 0
let right = _blocks.length
while (left + 1 < right) {
const mid = (left + right) >>> 1
if (this._compareFn(value, _mins[mid]) < 0) {
right = mid
} else {
left = mid
}
}
const pos = left
// find index
const cur = _blocks[pos]
left = -1
right = cur.length
while (left + 1 < right) {
const mid = (left + right) >>> 1
if (this._compareFn(value, cur[mid]) < 0) {
right = mid
} else {
left = mid
}
}
return [pos, right]
}
protected _locBlock(value: V): number {
let left = -1
let right = this._blocks.length - 1
while (left + 1 < right) {
const mid = (left + right) >>> 1
if (this._compareFn(value, this._mins[mid]) <= 0) {
right = mid
} else {
left = mid
}
}
if (right) {
const block = this._blocks[right - 1]
if (this._compareFn(value, block[block.length - 1]) <= 0) {
right--
}
}
return right
}
private _buildTree(): void {
this._tree = Array(this._blocks.length)
for (let i = 0; i < this._blocks.length; i++) {
this._tree[i] = this._blocks[i].length
}
const tree = this._tree
for (let i = 0; i < tree.length; i++) {
const j = i | (i + 1)
if (j < tree.length) {
tree[j] += tree[i]
}
}
this._shouldRebuildTree = false
}
protected _updateTree(index: number, delta: number): void {
if (!this._shouldRebuildTree) {
const tree = this._tree
while (index < tree.length) {
tree[index] += delta
index |= index + 1
}
}
}
private _queryTree(end: number): number {
if (this._shouldRebuildTree) this._buildTree()
const tree = this._tree
let x = 0
while (end) {
x += tree[end - 1]
end &= end - 1
}
return x
}
/**
* 树状数组树上二分, 找到索引为 `k` 的元素的`(所在块的索引pos, 块内的索引index)`.
* 内部对头部块和尾部块做了特殊处理.
*/
protected _findKth(k: number): [pos: number, index: number] {
if (k < this._blocks[0].length) return [0, k]
const last = this._blocks.length - 1
const lastLen = this._blocks[last].length
if (k >= this._len - lastLen) return [last, k + lastLen - this._len]
if (this._shouldRebuildTree) this._buildTree()
const tree = this._tree
let pos = -1
const bitLength = 32 - Math.clz32(tree.length)
for (let d = bitLength - 1; ~d; d--) {
const next = pos + (1 << d)
if (next < tree.length && k >= tree[next]) {
pos = next
k -= tree[pos]
}
}
return [pos + 1, k]
}
private _iteratorAt(pos: number, index: number): ISortedListIterator<V> {
const hasNext = (): boolean => {
return pos < this._blocks.length - 1 || index < this._blocks[pos].length - 1
}
const next = (): V | undefined => {
if (!hasNext()) return void 0
index++
if (index === this._blocks[pos].length) {
pos++
index = 0
}
return this._blocks[pos][index]
}
const hasPrev = (): boolean => {
return pos > 0 || index > 0
}
const prev = (): V | undefined => {
if (!hasPrev()) return void 0
index--
if (index === -1) {
pos--
index = this._blocks[pos].length - 1
}
return this._blocks[pos][index]
}
const remove = (): void => {
this._delete(pos, index)
}
// eslint-disable-next-line @typescript-eslint/no-this-alias
const sl = this
return {
hasNext,
next,
hasPrev,
prev,
remove,
get value(): V | undefined {
if (pos < 0 || pos >= sl.length) return void 0
const block = sl._blocks[pos]
if (index < 0 || index >= block.length) return void 0
return block[index]
}
}
}
}
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 IncrementalRectangleUnionRange()
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
}