結果

問題 No.1074 増殖
ユーザー htensaihtensai
提出日時 2020-06-10 10:01:40
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,115 ms / 2,000 ms
コード長 2,345 bytes
コンパイル時間 2,662 ms
コンパイル使用メモリ 81,508 KB
実行使用メモリ 69,376 KB
最終ジャッジ日時 2024-06-22 05:12:11
合計ジャッジ時間 12,616 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Area leftUp = new Area();
Area rightUp = new Area();
Area leftDown = new Area();
Area rightDown = new Area();
StringBuilder sb = new StringBuilder();
int prev = 0;
for (int i = 0; i < n; i++) {
int x1 = -sc.nextInt();
int y1 = -sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
int space = 0;
space += leftUp.get(x1, y2);
space += rightUp.get(x2, y2);
space += leftDown.get(x1, y1);
space += rightDown.get(x2, y1);
sb.append(space - prev).append("\n");
prev = space;
}
System.out.print(sb);
}
static class Area {
ArrayList<Piece> list = new ArrayList<>();
public Area() {
list.add(new Piece(1, 20000, 0));
}
public int get(int x, int y) {
for (int i = 0; i < list.size(); i++) {
Piece p = list.get(i);
if (p.left > x) {
break;
}
if (p.height >= y) {
continue;
}
if (p.right <= x) {
p.height = y;
} else {
list.add(i, new Piece(p.left, x, y));
p.left = x + 1;
break;
}
}
int idx = 1;
while (idx < list.size()) {
Piece left = list.get(idx - 1);
Piece right = list.get(idx);
if (left.height == right.height) {
left.right = right.right;
list.remove(idx);
} else {
idx++;
}
}
int space = 0;
for (Piece p : list) {
space += p.space();
}
return space;
}
public String toString() {
return list.toString();
}
}
static class Piece {
int left;
int right;
int height;
public Piece(int left, int right, int height) {
this.left = left;
this.right = right;
this.height = height;
}
public int space() {
return (right - left + 1) * height;
}
public String toString() {
return left + ":" + right + ":" + height;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0