結果

問題 No.1074 増殖
ユーザー htensaihtensai
提出日時 2020-06-10 10:01:40
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,045 ms / 2,000 ms
コード長 2,345 bytes
コンパイル時間 2,475 ms
コンパイル使用メモリ 82,656 KB
実行使用メモリ 64,900 KB
最終ジャッジ日時 2023-09-04 05:47:30
合計ジャッジ時間 10,913 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 121 ms
55,708 KB
testcase_01 AC 123 ms
56,248 KB
testcase_02 AC 121 ms
55,572 KB
testcase_03 AC 123 ms
55,624 KB
testcase_04 AC 126 ms
56,100 KB
testcase_05 AC 128 ms
56,012 KB
testcase_06 AC 639 ms
64,532 KB
testcase_07 AC 687 ms
64,900 KB
testcase_08 AC 648 ms
64,440 KB
testcase_09 AC 724 ms
64,508 KB
testcase_10 AC 645 ms
64,748 KB
testcase_11 AC 691 ms
64,736 KB
testcase_12 AC 714 ms
63,892 KB
testcase_13 AC 1,045 ms
64,668 KB
testcase_14 AC 1,023 ms
64,880 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