結果

問題 No.1074 増殖
ユーザー htensaihtensai
提出日時 2020-06-10 10:01:40
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 139 ms
53,900 KB
testcase_01 AC 141 ms
54,028 KB
testcase_02 AC 139 ms
54,152 KB
testcase_03 AC 138 ms
54,152 KB
testcase_04 AC 144 ms
54,108 KB
testcase_05 AC 144 ms
54,312 KB
testcase_06 AC 747 ms
60,848 KB
testcase_07 AC 785 ms
63,144 KB
testcase_08 AC 744 ms
62,624 KB
testcase_09 AC 846 ms
63,824 KB
testcase_10 AC 684 ms
63,648 KB
testcase_11 AC 747 ms
63,460 KB
testcase_12 AC 791 ms
63,500 KB
testcase_13 AC 1,115 ms
69,372 KB
testcase_14 AC 1,072 ms
69,376 KB
権限があれば一括ダウンロードができます

ソースコード

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;
	    }
	}
}
0