Untitled
unknown
plain_text
a year ago
3.3 kB
11
Indexable
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);
}
}Editor is loading...
Leave a Comment