Codeforces Round #310 Div1 C: Case of Chocolate

問題

codeforces.com

解法

各(x,y,UL)クエリに対して、一番近い右のクエリを見れば欲しい情報が書いてあるようにしておく。

コード

import java.util.Scanner;
import java.util.TreeMap;

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

		// 自分よりx座標の小さいクエリが来た時にどこが壁になるか、を記録する
		TreeMap<Integer, Wall> wallMap = new TreeMap<>();
		wallMap.put(N + 1, new Wall(0, 0));

		StringBuilder builder = new StringBuilder();
		for (int q = 0; q < Q; q++) {
			int x = scanner.nextInt();
			int y = scanner.nextInt();
			String s = scanner.next();

			if (wallMap.containsKey(x)) {
				// 処理したことのあるクエリなら、チョコは残っていないはず
				builder.append(0 + "\n");
				continue;
			}

			// 自分より右側にある処理済みのクエリを読む
			Wall higherWall = wallMap.get(wallMap.higherKey(x));
			if (s.equals("U")) {
				// 上向き食べる時
				builder.append(y - higherWall.y + "\n");
				wallMap.put(x, new Wall(higherWall.y, higherWall.x));

				// 今後xとhigherWall.xの間で左に行こうとすると、xが壁になる
				higherWall.x = x;
			} else {
				// 左向きに食べる時
				builder.append(x - higherWall.x + "\n");
				wallMap.put(x, new Wall(y, higherWall.x));
			}
		}
		System.out.println(builder.toString());
		scanner.close();
	}

	private class Wall {
		int y, x;

		public Wall(int y, int x) {
			this.x = x;
			this.y = y;
		}
	}

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