Submission #70981670

---

Source Code Expand

import java.io.*;
import java.util.*;

public class Main {

    static class Rectangle {
        long x1, x2, y1, y2;

        Rectangle(long x1, long x2, long y1, long y2) {
            this.x1 = x1;
            this.x2 = x2;
            this.y1 = y1;
            this.y2 = y2;
        }

        long size() {
            if (x1 > x2 || y1 > y2) {
                return 0;
            }
            return (x2 - x1 + 1) * (y2 - y1 + 1);
        }

        boolean isValid() {
            return x1 <= x2 && y1 <= y2;
        }
    }

    static boolean checkOverlap(long a1, long a2, long b1, long b2) {
        return Math.max(a1, b1) <= Math.min(a2, b2);
    }

    static boolean areAdjacent(Rectangle r1, Rectangle r2) {
        if (checkOverlap(r1.x1, r1.x2, r2.x1, r2.x2)) {
            if (r1.y2 + 1 == r2.y1 || r2.y2 + 1 == r1.y1) {
                return true;
            }
        }
        if (checkOverlap(r1.y1, r1.y2, r2.y1, r2.y2)) {
            if (r1.x2 + 1 == r2.x1 || r2.x2 + 1 == r1.x1) {
                return true;
            }
        }
        return false;
    }

    static class UnionFind {
        int[] parent;
        int count;

        UnionFind(int n) {
            parent = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                count--;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long X = Long.parseLong(st.nextToken());
        long Y = Long.parseLong(st.nextToken());

        char[] C = new char[N];
        long[] A = new long[N];
        long[] B = new long[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            C[i] = st.nextToken().charAt(0);
            A[i] = Long.parseLong(st.nextToken());
            B[i] = Long.parseLong(st.nextToken());
        }

        List<Rectangle> rects = new ArrayList<>();
        rects.add(new Rectangle(0, X - 1, 0, Y - 1));

        for (int i = 0; i < N; i++) {
            List<Rectangle> nextRects = new ArrayList<>();
            long Ai = A[i];
            long Bi = B[i];

            for (Rectangle r : rects) {
                if (C[i] == 'X') {
                    Rectangle r1 = new Rectangle(r.x1, Math.min(r.x2, Ai - 1), r.y1 - Bi, r.y2 - Bi);
                    Rectangle r2 = new Rectangle(Math.max(r.x1, Ai), r.x2, r.y1 + Bi, r.y2 + Bi);
                    if (r1.isValid()) nextRects.add(r1);
                    if (r2.isValid()) nextRects.add(r2);
                } else {
                    Rectangle r1 = new Rectangle(r.x1 - Bi, r.x2 - Bi, r.y1, Math.min(r.y2, Ai - 1));
                    Rectangle r2 = new Rectangle(r.x1 + Bi, r.x2 + Bi, Math.max(r.y1, Ai), r.y2);
                    if (r1.isValid()) nextRects.add(r1);
                    if (r2.isValid()) nextRects.add(r2);
                }
            }
            rects = nextRects;
        }

        int K = rects.size();
        if (K == 0) {
            System.out.println(0);
            System.out.println();
            return;
        }
        
        UnionFind uf = new UnionFind(K);
        for (int i = 0; i < K; i++) {
            for (int j = i + 1; j < K; j++) {
                if (areAdjacent(rects.get(i), rects.get(j))) {
                    uf.union(i, j);
                }
            }
        }

        Map<Integer, Long> componentSizes = new HashMap<>();
        for (int i = 0; i < K; i++) {
            int root = uf.find(i);
            long size = rects.get(i).size();
            componentSizes.put(root, componentSizes.getOrDefault(root, 0L) + size);
        }

        List<Long> sizes = new ArrayList<>(componentSizes.values());
        Collections.sort(sizes);

        PrintWriter pw = new PrintWriter(System.out);
        pw.println(sizes.size());
        for (int i = 0; i < sizes.size(); i++) {
            pw.print(sizes.get(i));
            if (i < sizes.size() - 1) {
                pw.print(" ");
            }
        }
        pw.println();
        pw.flush();
    }
}

Submission Info

Judge Result