Untitled

mail@pastecode.io avatar
unknown
plain_text
19 days ago
3.3 kB
2
Indexable
Never
import java.util.*;

class Node {
        int start, end;
        Integer[] X;
        Node left, right;
        int count;
        long total;

        public Node(int start, int end, Integer[] X) {
            this.start = start;
            this.end = end;
            this.X = X;
            left = null;
            right = null;
            count = 0;
            total = 0;
        }

        public int getRangeMid() {
            return start + (end - start) / 2;
        }

        public Node getLeft() {
            if (left == null) left = new Node(start, getRangeMid(), X);
            return left;
        }

        public Node getRight() {
            if (right == null) right = new Node(getRangeMid(), end, X);
            return right;
        }

        public long update(int i, int j, int val) {
            if (i >= j) return 0;
            if (start == i && end == j) {
                count += val;
            } else {
                getLeft().update(i, Math.min(getRangeMid(), j), val);
                getRight().update(Math.max(getRangeMid(), i), j, val);
            }

            if (count > 0) total = X[end] - X[start];
            else total = getLeft().total + getRight().total;

            return total;
        }
}

public class RectangleArea {

    public long findArea(int n, int[][] rectangles){


     //  USING SEGMENT TREE

      if (n == 1) {
        // Special case for a single rectangle
        int[] rec = rectangles[0];
        if (rec[0] < rec[2] && rec[1] < rec[3]) {
            return (long) (rec[2] - rec[0]) * (rec[3] - rec[1]) % 1_000_000_007;
        }
        return 0;
    }

    int OPEN = 1, CLOSE = -1;
    int[][] events = new int[rectangles.length * 2][];
    Set<Integer> Xvals = new HashSet<>();
    int t = 0;
    for (int[] rec: rectangles) {
        if ((rec[0] < rec[2]) && (rec[1] < rec[3])) {
            events[t++] = new int[]{rec[1], OPEN, rec[0], rec[2]};
            events[t++] = new int[]{rec[3], CLOSE, rec[0], rec[2]};
            Xvals.add(rec[0]);
            Xvals.add(rec[2]);
        }
    }

    Arrays.sort(events, 0, t, (a, b) -> Integer.compare(a[0], b[0]));

    Integer[] X = Xvals.toArray(new Integer[0]);
    Arrays.sort(X);
    Map<Integer, Integer> Xi = new HashMap();
    for (int i = 0; i < X.length; ++i)
        Xi.put(X[i], i);

    Node active = new Node(0, X.length - 1, X);
    long ans = 0;
    long cur_x_sum = 0;
    int cur_y = events[0][0];
    
    for (int[] event: events) {
        if (event == null) break;
        int y = event[0], typ = event[1], x1 = event[2], x2 = event[3];
        ans += cur_x_sum * (y - cur_y);
        cur_x_sum = active.update(Xi.get(x1), Xi.get(x2), typ);
        cur_y = y;
    }

    ans %= 1_000_000_007;
    return  ans;
}
    

    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[][] rectangles = new int[n][4];

        for(int i = 0 ; i < n ;i++) {
            rectangles[i][0] = scanner.nextInt();
            rectangles[i][1] = scanner.nextInt();
            rectangles[i][2] = scanner.nextInt();
            rectangles[i][3] = scanner.nextInt();
        }
	scanner.close();

        long result = new RectangleArea().findArea(n, rectangles);
        System.out.print(result);
    }
}
Leave a Comment