ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1147. Shaping Regions

N^2*log N solution gets TLE
Posted by Vitalii Arbuzov 9 Apr 2011 00:42
Hi all, i've used segment tree to solve this problem and got stuck with TLE 11.
Maybe someone have idea of how to improve this solution to fit in time. Or one can provide test data that will get TLE locally.

import java.util.Scanner;

public class P1147 {

    private static final int MAX_COLORS = 2501;
    private static final short UNKNOWN = 0;
    private static long c[] = new long[MAX_COLORS];
    private static final int TREE_SIZE = 1<<22;
    private static final int PARTITION_FACTOR = 10;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        short a = scanner.nextShort();
        short b = scanner.nextShort();
        short n = scanner.nextShort();
        short[] tree = new short[TREE_SIZE];
        Rectangle[] rectangles = new Rectangle[n + 1];
        rectangles[0] = new Rectangle(0, 0, a, b, 1);
        for (short i = 1; i <= n; i++) {
            rectangles[i] =  new Rectangle(scanner.nextShort(), scanner.nextShort(), scanner.nextShort(), scanner.nextShort(), scanner.nextShort());
        }
        for (double iPartition = 0; iPartition < PARTITION_FACTOR - 1e-6; iPartition++) {
            for (double jPartition = 0; jPartition < PARTITION_FACTOR - 1e-6; jPartition++) {
                Rectangle partition = new Rectangle((int) (a * (iPartition / PARTITION_FACTOR)), (int) (b * (jPartition / PARTITION_FACTOR)), (int) (a * ((iPartition + 1) / PARTITION_FACTOR)), (int) (b * ((jPartition + 1) / PARTITION_FACTOR)));
                for (Rectangle rectangle : rectangles) {
                    insert(tree, 0, rectangle, partition);
                }
                countColors(tree, 0, partition);
            }
        }
        for (int i = 0; i < MAX_COLORS; i++) {
            if (c[i] != 0) {
                System.out.println(i + " " + c[i]);
            }
        }
    }

    static void insert(short[] tree, int node, Rectangle rect, Rectangle region) {
        if (!rect.intersects(region) || !rect.isValid() || !region.isValid()) return;
        if (rect.contains(region)) {
            tree[node] = rect.color;
        } else {
            if (tree[node] == UNKNOWN) {
                int xMid = (region.x1 + region.x2) / 2;
                int yMid = (region.y1 + region.y2) / 2;
                insert(tree, node * 4 + 1, rect, new Rectangle(region.x1, region.y1, xMid, yMid));
                insert(tree, node * 4 + 2, rect, new Rectangle(xMid,  region.y1, region.x2, yMid));
                insert(tree, node * 4 + 3, rect, new Rectangle(xMid, yMid, region.x2, region.y2));
                insert(tree, node * 4 + 4, rect, new Rectangle(region.x1, yMid, xMid, region.y2));
            } else {
                if (tree[node] == rect.color) return;
                Rectangle bottom = new Rectangle(region.x1, region.y1, region.x2, rect.y1, tree[node]);
                Rectangle top = new Rectangle(region.x1, rect.y2, region.x2, region.y2, tree[node]);
                Rectangle left = new Rectangle(region.x1, rect.y1, rect.x1, rect.y2, tree[node]);
                Rectangle right = new Rectangle(rect.x2, rect.y1, region.x2, rect.y2, tree[node]);
                tree[node] = UNKNOWN;
                insert(tree, node, rect, region);
                insert(tree, node, bottom, region);
                insert(tree, node, top, region);
                insert(tree, node, left, region);
                insert(tree, node, right, region);


        }
    }

    private static void countColors(short[] tree, int node, Rectangle region) {
        if (!region.isValid()) return;
        if (node >= TREE_SIZE) return;
        if (tree[node] != UNKNOWN) {
            c[tree[node]] += region.area();
        } else {
            int xMid = (region.x1 + region.x2) / 2;
            int yMid = (region.y1 + region.y2) / 2;
            countColors(tree, node * 4 + 1, new Rectangle(region.x1, region.y1, xMid, yMid));
            countColors(tree, node * 4 + 2, new Rectangle(xMid, region.y1, region.x2, yMid));
            countColors(tree, node * 4 + 3, new Rectangle(xMid, yMid, region.x2, region.y2));
            countColors(tree, node * 4 + 4, new Rectangle(region.x1, yMid, xMid, region.y2));
        }
    }

    static class Rectangle {
        short x1, y1, x2, y2, color;

        Rectangle(int x1, int y1, int x2, int y2, int color) {
            this.x1 = (short) x1;
            this.y1 = (short) y1;
            this.x2 = (short) x2;
            this.y2 = (short) y2;
            this.color = (short) color;
        }

        public Rectangle(int x1, int y1, int x2, int y2) {
            this(x1, y1, x2, y2, UNKNOWN);
        }

        boolean intersects(Rectangle other) {
            return other.x1 < this.x2 && other.x2 > this.x1 && other.y1 < this.y2 && other.y2 > this.y1;
        }

        boolean contains(Rectangle other) {
            return (other.x1 >= this.x1) && (other.x2 <= this.x2) && (other.y1 >= this.y1) && (other.y2 <= this.y2);
        }

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

        long area() {
            return (x2 - x1) * (y2 - y1);
        }
    }
}

Many thanks,

Vitaliy