結果

問題 No.1074 増殖
コンテスト
ユーザー htensai
提出日時 2020-06-10 09:58:48
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 9
権限があれば一括ダウンロードができます

ソースコード

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