結果
問題 | No.1074 増殖 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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;}}}