結果

問題 No.1074 増殖
ユーザー semisagisemisagi
提出日時 2020-06-05 22:06:59
言語 Swift
(5.10.0)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 2,559 bytes
コンパイル時間 8,240 ms
コンパイル使用メモリ 136,012 KB
実行使用メモリ 15,960 KB
最終ジャッジ日時 2023-08-20 15:25:53
合計ジャッジ時間 5,556 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,904 KB
testcase_01 AC 3 ms
7,936 KB
testcase_02 AC 3 ms
7,832 KB
testcase_03 AC 3 ms
7,848 KB
testcase_04 AC 3 ms
7,800 KB
testcase_05 AC 3 ms
7,804 KB
testcase_06 AC 115 ms
15,852 KB
testcase_07 AC 116 ms
15,888 KB
testcase_08 AC 105 ms
15,948 KB
testcase_09 AC 121 ms
15,960 KB
testcase_10 AC 120 ms
15,828 KB
testcase_11 AC 117 ms
15,944 KB
testcase_12 AC 117 ms
15,932 KB
testcase_13 AC 139 ms
15,876 KB
testcase_14 AC 138 ms
15,864 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class Scanner {
    private var stack = [String]()
    private var index = 0
    
    func peek() -> String {
        if stack.count == index {
            stack += readLine()!.split(separator: " ").map{ String($0) }
        }
        return stack[index]
    }
    
    func next() -> String {
        let value = peek()
        index += 1
        return value
    }
    
    func nextInt() -> Int {
        return Int(next())!
    }
    
    func nextDouble() -> Double {
        return Double(next())!
    }
}

extension String {
    var characters: [Character] {
        self.map{ $0 }
    }
}

// 問題を象限ごとに分解する

var scanner = Scanner()
let N = scanner.nextInt()

struct Point {
    let x: Int
    let y: Int
}

var A = [(x1: Int, y1: Int, x2: Int, y2: Int)]()
for _ in 0 ..< N {
    let x1 = scanner.nextInt()
    let y1 = scanner.nextInt()
    let x2 = scanner.nextInt()
    let y2 = scanner.nextInt()
    A.append((x1: x1, y1: y1, x2: x2, y2: y2))
}

struct MyDataStructure {
    var points = [Point(x: 0, y: 100000), Point(x: 100000, y: 0)]
    var area = 0
    
    func dominate(_ p: Point, _ q: Point) -> Bool {
        p.x <= q.x && p.y <= q.y
    }
    
    mutating func remove(point p: Point) {
        main: while true {
            for i in 0 ..< points.count {
                if dominate(points[i], p) {
                    area -= (points[i].x - points[i - 1].x) * (points[i].y - points[i + 1].y)
                    points.remove(at: i)
                    continue main
                }
            }
            break
        }
    }

    mutating func insert(point p: Point) {
        remove(point: p)
        var i = 0
        while i < points.count {
            if points[i].x < p.x {
                i += 1
            } else {
                break
            }
        }
        if !dominate(p, points[i]) {
            area += (p.x - points[i - 1].x) * (p.y - points[i].y)
            points.insert(p, at: i)
        }
    }
}

func count(points: [Point]) -> [Int] {
    var value = [Int]()
    var my = MyDataStructure()
    for point in points {
        let previousArea = my.area
        my.insert(point: point)
        value.append(my.area - previousArea)
    }
    return value
}

let answer = [
    A.map{ a in Point(x: -a.x1, y: -a.y1) },
    A.map{ a in Point(x: -a.x1, y: a.y2) },
    A.map{ a in Point(x: a.x2, y: -a.y1) },
    A.map{ a in Point(x: a.x2, y: a.y2) }].map(count)

for i in 0 ..< N {
    var value = 0
    for j in 0 ..< 4 {
        value += answer[j][i]
    }
    print(value)
}
0