Codeforces Round #296 Div2 C: Glass Carving

問題

codeforces.com

解法

• クエリ処理のたびに、最大の高さと、最大の幅を知りたい。
• 切られるたびに1つ辺が減り、2つ新しい辺が出来る。

以下、縦に切った場合を考える。

• w0の長さの辺が切られ、新たにw1とw2の長さの辺が出来るとする。
• 辺の種類と数を管理しておき、w0の辺が最後のひとつだったらリストから削除する。
• w1とw2が存在しなかった場合、リストに追加しておく。

コード

import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	public void solve() {
		Scanner scanner = new Scanner(System.in);
		int W = scanner.nextInt();
		int H = scanner.nextInt();
		int Q = scanner.nextInt();

		int[] wCnt = new int[W + 1];// wCnt[i]:= 幅iのピースの数
		wCnt[W]++;
		int[] hCnt = new int[H + 1];
		hCnt[H]++;

		// 切れ込みの入った座標をTreeSetに入れておく
		TreeSet<Integer> wCutSet = new TreeSet<>();
		wCutSet.add(0);
		wCutSet.add(W);
		TreeSet<Integer> hCutSet = new TreeSet<>();
		hCutSet.add(0);
		hCutSet.add(H);

		// ピースの幅をTreeSetに入れておく
		TreeSet<Integer> wLengthSet = new TreeSet<>();
		wLengthSet.add(W);
		TreeSet<Integer> hLengthSet = new TreeSet<>();
		hLengthSet.add(H);

		StringBuilder sb = new StringBuilder();
		for (int q = 0; q < Q; q++) {
			String operation = scanner.next();
			int point = scanner.nextInt();

			if (operation.equals("H")) {
				cutBoard(hCnt, hCutSet, hLengthSet, point);
			} else {
				cutBoard(wCnt, wCutSet, wLengthSet, point);
			}
			long largest = (long) wLengthSet.last() * hLengthSet.last();
			sb.append(largest + "\n");
		}
		System.out.print(sb.toString());
		scanner.close();
	}

	private void cutBoard(int[] cnt, TreeSet<Integer> cutSet,
			TreeSet<Integer> lenghtSet, int point) {
		// これから入れる切り込みの直前にある切れ込みの座標
		int low = cutSet.floor(point);

		// これから入れる切り込みの直後にある切れ込みの座標
		int high = cutSet.ceiling(point);

		// これから切られる辺の長さ
		int lenght = high - low;

		// 切れ込み座標を記録しておく
		cutSet.add(point);

		// lengthの辺をもつピースは1つ切られて減った
		cnt[lenght]--;
		if (cnt[lenght] == 0) {
			// lengthの辺をもつピースが1つもなくなったら削除しておく
			lenghtSet.remove(lenght);
		}
		
		// 新しく出来たピースを追加しておく
		if (cnt[high - point] == 0) {
			lenghtSet.add(high - point);
		}
		cnt[high - point]++;
		if (cnt[point - low] == 0) {
			lenghtSet.add(point - low);
		}
		cnt[point - low]++;
	}

	public static void main(String[] args) {
		new Main().solve();
	}
}