結果

問題 No.1074 増殖
コンテスト
ユーザー semisagi
提出日時 2020-06-05 22:06:59
言語 Swift
(6.0.3)
結果
AC  
実行時間 182 ms / 2,000 ms
コード長 2,559 bytes
コンパイル時間 1,701 ms
コンパイル使用メモリ 132,800 KB
実行使用メモリ 17,300 KB
最終ジャッジ日時 2024-11-30 18:25:42
合計ジャッジ時間 4,822 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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