結果

問題 No.1074 増殖
ユーザー htensaihtensai
提出日時 2020-06-10 09:58:48
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,345 bytes
コンパイル時間 2,170 ms
コンパイル使用メモリ 80,360 KB
実行使用メモリ 69,500 KB
最終ジャッジ日時 2024-06-22 05:03:42
合計ジャッジ時間 10,779 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 119 ms
54,000 KB
testcase_01 AC 118 ms
54,032 KB
testcase_02 AC 115 ms
53,960 KB
testcase_03 AC 105 ms
52,752 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 625 ms
62,960 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 582 ms
63,620 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
権限があれば一括ダウンロードができます

ソースコード

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 = x;
	            } 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