I can not find the error. Share the tests, please

My solution way getting TLE - on test 32 - while my complexity was O(n ^ 2) I think;
but by changing some parameters - coordinates for example - from int to short int, (a 4 byte variable to a 2 byte one) got AC in .3 s.
I thought may help you!
Good luck :)

For N^2 log N solutions. All this can cause you because of antiquicksort test, I think. After I changed sort to stable_sort, everything started to work better. It depends on compiler also. On USACO I had RE #4.

New timelimit is 0.5 seconds. All solutions were rejudged.

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

first i use RB tree (set in C++) and got AC in 0.796s and when i use heap i AC in 0.156s. my algo is (n^2* log(n)).
GOOD LUCK!!!

this my code:
import java.io.*;
import java.util.*;

public class Problem_1147 implements Runnable{
    public static void main(String []args){
        new Thread(new Problem_1147()).start();
    }
    public void run(){
        try{
            reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            //reader = new StreamTokenizer(new BufferedReader(new FileReader("card.out")));
            //out = new PrintWriter(new FileWriter("card.out"));
            solve();
        }catch(IOException e){
            throw new IllegalStateException(e);
        }
    }

    final int COLOR_COUNT = 5501;
    final int N = 400001;
    int n;
    int width;
    int height;

    int xPos[] = new int[10001];
    int yPos[] = new int[10001];

    int color[] = new int[COLOR_COUNT];
    int x[]      = new int[1001];
    int y[]     = new int[1001];
    int z[]      = new int[1001];
    int t[]     = new int[1001];
    int cc[]    = new int[1001];
    int xc[] = new int[1009];
    int yc[] = new int[1009];

    short tColor[][] = new short[2002][2002];

    StreamTokenizer reader;

    PrintWriter out;

    int nextInt()throws IOException{
        reader.nextToken();
        return(int)reader.nval;

    }







    void solve()throws IOException{

        width = nextInt();
        height  = nextInt();
        n = nextInt();

        for (int i = 1; i<=n;i++){
            x[i] = nextInt();
            y[i] = nextInt();
            z[i] = nextInt();
            t[i] = nextInt();

            cc[i] = nextInt();
        }
        x[0] = 0;
        y[0] = 0;
        z[0] = width;
        t[0] = height;
        cc[0] = 1;

        Arrays.fill(xPos,0);
        Arrays.fill(yPos,0);

        for (int i = 0;i <=n ;i++)xPos[x[i]] = xPos[z[i]] = yPos[y[i]] = yPos[t[i]] = 1;



        for (int i = 1; i<= width; i++)xPos[i] += xPos[i-1];
        for (int i = 1; i<= height; i++)yPos[i] += yPos[i-1];

        for (int i = width; i >= 0  ; i-- ) xc[xPos[i]] = i ;
        for (int i = height; i>= 0  ; i-- ) yc[yPos[i]] = i ;

    /*    System.out.println("x coords ");
        for (int i = xPos[0] ; i<=xPos[width];i++)System.out.println(xc[i]);
        System.out.println("y coords ");
        for (int i = yPos[0] ; i<=yPos[height];i++)System.out.println(yc[i]);
    */
        for (int i = 0; i<=n;i++){
            int i_x = xPos[x[i]];
            int j_x = xPos[z[i]];
            int i_y = yPos[y[i]];
            int j_y = yPos[t[i]];
            short c = (short)cc[i];
        //    System.out.println(i_x +" " +j_x+" " +i_y+" " +j_y);
            for (int v = i_x; v < j_x; v++){
                for (int w = i_y; w  < j_y; w++){
                    tColor[v][w] = c;
                }
            }
        }

        Arrays.fill(color, 0);
        for (int i = xPos[0]; i < xPos[width]; i++){
            for (int j = yPos[0]; j < yPos[height]; j++){
                color[tColor[i][j]] += (xc[i+1] - xc[i])*(yc[j+1] - yc[j]);
            }
        }

        for (int i = 1; i<=2500;i++)if (color[i]>0)System.out.println(i+ " "+color[i]);
    }

}

This is my "var"

const
  big=3000;
var
  i,j,k,l,m,n,l1,l2,now,sum,res,last:longint;
  f:array[1..big,1..2000]of integer;
  ans:array[1..2500]of longint;
  a:array[1..2000]of record
                       x1,y1,x2,y2,col:longint;
                     end;
  x:array[1..2,0..2000]of longint;
  mi:array[1..2,0..10000]of longint;

I think I only use about 12MB memory,but the system told me that I got MLE on test 1.
Why?Why?

Help!
Thanks.

Edited by author 09.06.2006 18:06

It seems like the limits for input values given in problem statement are incorrect - after changing data types from short int (which have max value larger than 30000) to int I got AC for test cases 2..16 - in opposite to the version before this change. So the WA was caused by numbers at input larger than 30000 - it shouldn't happen.

Am I wrong or should it be fixed?

1003 1003 1000
1 2 1002 3 2
2 1 3 1002 3
1 4 1002 5 2
4 1 5 1002 3
1 6 1002 7 2
6 1 7 1002 3
1 8 1002 9 2
8 1 9 1002 3
...
1 992 1002 993 2
992 1 993 1002 3
1 994 1002 995 2
994 1 995 1002 3
1 996 1002 997 2
996 1 997 1002 3
1 998 1002 999 2
998 1 999 1002 3
1 1000 1002 1001 2
1000 1 1001 1002 3

This test was in previous subject, but I don't know
the correct answer!
Mine is:
1 165320
2 34966
3 34214

P. S. I have WA#17 with no thoughts!

Thanks.

Can you give me an expaination that it's clear?
I means which is X and wich is Y?

Hi,
I just passed Tests of USACO, and then I saw this beautiful solution in "Analysis".Then I tried to implement it. But then I got TLE on test #17 ( in USACO, I submitted this sol, and it runs 10 times faster than N^2logN ). I'm wondering, if this Algo is N^3 . Is it true ?
(Sorry for my bad English :p )

Hier is the code :

//TLE : #17 acm ru, but 10 times faster in USACO (in comparasion to Heap Algo)
#include <iostream>
#include <vector>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;i++)
#define CLEAR(A) memset(A,0,sizeof(A))
#define FILL(A,v) fill(A.begin(),A.end(),v)
const   int maxn = 1002;
const   int maxC = 2502;

class Rect {
      public: int x1,y1,x2,y2,c;
              Rect() {}
              Rect(int xx1,int yy1,int xx2,int yy2,int cc)
              { x1=xx1;x2=xx2;y1=yy1;y2=yy2;c=cc; }
};
vector<int> area(maxC);
int         N;
vector<Rect>  rect(0);
void Partition(int id,Rect R)
{   if (R.x1 >= R.x2 || R.y1 >= R.y2 ) return;
    if (id   >  N                    )
       { area[R.c] += (R.x2-R.x1)*(R.y2-R.y1); return; }
    if (R.x1 >= rect[id].x2 || R.x2 <= rect[id].x1 ||
        R.y1 >= rect[id].y2 || R.y2 <= rect[id].y1)       Partition(id+1,R);
    else{
        if (rect[id].x2 < R.x2 ) Partition(id+1,Rect(rect[id].x2,R.y1,R.x2,R.y2,R.c));
        if (rect[id].x1 > R.x1 ) Partition(id+1,Rect(R.x1,R.y1,rect[id].x1,R.y2,R.c));
        if (rect[id].y1 > R.y1 ) Partition(id+1,Rect(max(R.x1,rect[id].x1),R.y1,min(R.x2,rect[id].x2),rect[id].y1,R.c));
        if (rect[id].y2 < R.y2 ) Partition(id+1,Rect(max(R.x1,rect[id].x1),rect[id].y2,min(R.x2,rect[id].x2),R.y2,R.c));
    }
}
int main()
{   FILL(area,0);
    int A,B,x1,y1,x2,y2,c;
    cin>> A >> B >> N; rect.resize(N+1);
    rect[0] = Rect(0,0,A,B,1);
    for(int i=1;i<=N;i++)
    { cin>>x1>>y1>>x2>>y2>>c; rect[i]=Rect(x1,y1,x2,y2,c); }
    for(int i=0;i<=N;i++) Partition(i+1,rect[i]);
    for(int i=1;i<maxC;i++)
        if (area[i] > 0) cout<<i<<" "<<area[i]<<endl;
    return 0;
}

Hi!
I have AC at USACO, nut here I have WA#17...
What's wrong?
Thanks

Edited by author 03.06.2006 18:19

New tests are harder. Only O(n n log n) solutions and better will work now.
Problem was rejudged.

add this test please

10 10 5
5 5 6 9 12
3 1 5 7 16
3 2 6 4 33
0 1 6 8 6
0 7 4 9 28


My AC out

1 54
6 38
12 1
28 8

54+38+1+8=101  (100% incorect)
correct out
1 53
6 38
12 1
28 8

53+38+1+8=100

If someone has a better solution,
would you please write it down?
Thanks.

program ural1147;
const
  maxn=1000;
  maxc=2500;
type
  pointer=^node;
  node=record
    l,r,b,t,c:word;
    lb,rb,lt,rt:pointer;
  end;
var
  x1,y1,x2,y2,color:array[0..maxn]of word;
  lx,ly:array[0..maxn*2+2]of word;
  area:array[1..maxc]of longint;
  n,i,t:word;
  root:pointer;
procedure qsort(var a:array of word;s,t:word);
  var
    p,i,j,tmp:word;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tmp:=a[p];a[p]:=a[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>=tmp) do dec(j);
      if i=j then break;a[i]:=a[j];inc(i);
      while (i<j) and (a[i]<=tmp) do inc(i);
      if i=j then break;a[j]:=a[i];dec(j);
    until i=j;
    a[i]:=tmp;
    qsort(a,s,i-1);
    qsort(a,i+1,t);
  end;
procedure makelines(var a,b,l:array of word);
  var
    i:word;
  begin
    for i:=0 to n do begin
      l[i*2+1]:=a[i];l[i*2+2]:=b[i];
    end;
    qsort(l,1,n*2+2);
    l[0]:=1;
    for i:=2 to n*2+2 do
      if l[i]>l[i-1] then begin
        inc(l[0]);
        l[l[0]]:=l[i];
      end;
  end;
function search(l:array of word;x:word):word;
  var
    s,t,m:word;
  begin
    s:=1;t:=l[0];
    repeat
      m:=(s+t) shr 1;
      if l[m]=x then break;
      if l[m]<x then s:=m+1 else t:=m-1;
    until false;
    search:=m;
  end;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:word):word;
  begin
    if a>b then max:=a else max:=b;
  end;
procedure recycle(p:pointer);
  begin
    if p=nil then exit;
    recycle(p^.lb);recycle(p^.rb);recycle(p^.lt);recycle(p^.rt);
    dispose(p);
  end;
procedure cover(p:pointer;sx,tx,sy,ty,clr:word);
  var
    mx,my:word;
  begin
    if (sx>=tx) or (sy>=ty) then exit;
    if p^.c=clr then exit;
    if (sx=p^.l) and (tx=p^.r) and (sy=p^.b) and (ty=p^.t) then begin
      p^.c:=clr;
      recycle(p^.lb);recycle(p^.rb);recycle(p^.lt);recycle(p^.rt);
      with p^ do begin lb:=nil;rb:=nil;lt:=nil;rt:=nil;end;
      exit;
    end;

    mx:=(p^.l+p^.r) shr 1;my:=(p^.b+p^.t) shr 1;
    if p^.c>0 then begin
      new(p^.lb);with p^.lb^ do begin l:=p^.l;r:=mx;b:=p^.b;t:=my;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end;
      new(p^.rb);with p^.rb^ do begin l:=mx;r:=p^.r;b:=p^.b;t:=my;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end;
      new(p^.lt);with p^.lt^ do begin l:=p^.l;r:=mx;b:=my;t:=p^.t;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end;
      new(p^.rt);with p^.rt^ do begin l:=mx;r:=p^.r;b:=my;t:=p^.t;c:=p^.c;lb:=nil;rb:=nil;lt:=nil;rt:=nil;end;
      p^.c:=0;
    end;
    cover(p^.lb,sx,min(mx,tx),sy,min(my,ty),clr);
    cover(p^.rb,max(mx,sx),tx,sy,min(my,ty),clr);
    cover(p^.lt,sx,min(mx,tx),max(my,sy),ty,clr);
    cover(p^.rt,max(mx,sx),tx,max(my,sy),ty,clr);
  end;
procedure stat(p:pointer);
  begin
    if p^.c>0 then
      inc(area[p^.c],(lx[p^.r]-lx[p^.l])*(ly[p^.t]-ly[p^.b]))
    else begin
      stat(p^.lb);stat(p^.rb);stat(p^.lt);stat(p^.rt);
    end;
  end;
begin
  x1[0]:=0;y1[0]:=0;read(x2[0],y2[0],n);
  for i:=1 to n do
    read(x1[i],y1[i],x2[i],y2[i],color[i]);

  makelines(x1,x2,lx);
  makelines(y1,y2,ly);

  new(root);
  with root^ do begin
    l:=1;r:=lx[0];b:=1;t:=ly[0];c:=1;
    lb:=nil;rb:=nil;lt:=nil;rt:=nil;
  end;

  for i:=1 to n do
    cover(root,search(lx,x1[i]),search(lx,x2[i]),search(ly,y1[i]),search(ly,y2[i]),color[i]);

  fillchar(area,sizeof(area),0);
  stat(root);

  for i:=1 to maxc do
    if area[i]>0 then
      writeln(i,' ',area[i]);
end.

For ~2 of the testcases (on USACO training for same problem), I get a
weird overlap, and my area for one of the colours is a bit bigger
than that of the real output. Can anyone tell me where my mistake is?
Here's my algorithm, which basically reads in the rectangles and is
supposed to go back through existing rectangles and reshape them so
that there is no overlap.
----------------------------------------------


#include <fstream.h>
#include <stdlib.h>

struct rect
{
 int x1; int y1; int x2; int y2;
 int c;
 bool v;
};

int main()
{
      rect sheets[10001];
      rect cur;
      int curTotal = 0;
      int A, B, N; //A = horizontal, B = vertical
      fstream infile, outfile;
      infile.open("rect1.in", ios::in);
      outfile.open("rect1.out", ios::out);

      infile >> A >> B >> N;

      sheets[0].x1 = 0; sheets[0].x2 = A;
      sheets[0].y1 = 0; sheets[0].y2 = B;
      sheets[0].c = 1; sheets[0].v = true;
      curTotal++;

      for (int i = 0; i < N; i++)
          {
           infile >> cur.x1 >> cur.y1 >> cur.x2 >> cur.y2 >> cur.c;
           //cout << cur.x1 << ' ' << cur.y1 << ' ' << cur.x2 << ' '
<< cur.x2 << ' ' << cur.c << endl;

           for (int j = 0; j < curTotal; j++)
               {
                if (!sheets[j].v) continue;
                //check for simple cases(i.e intersect at a side)
                if (sheets[j].x1 < cur.x1 && sheets[j].x2 > cur.x1 &&
sheets[j].x2 <= cur.x2 && sheets[j].y1 >= cur.y1 && sheets[j].y2 <=
cur.y2)
                   { sheets[j].x2 = cur.x1; continue; }
                if (sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 &&
sheets[j].y2 <= cur.y2 && sheets[j].x1 >= cur.x1 && sheets[j].x2 <=
cur.x2)
                   { sheets[j].y2 = cur.y1; continue; }
                if (sheets[j].x2 > cur.x2 && sheets[j].x1 < cur.x2 &&
sheets[j].x1 >= cur.x1 && sheets[j].y1 >= cur.y1 && sheets[j].y2 <=
cur.y2)
                   { sheets[j].x1 = cur.x2; continue; }
                if (sheets[j].y2 > cur.y2 && sheets[j].y1 < cur.y2 &&
sheets[j].y1 >= cur.y1 && sheets[j].x1 >= cur.x1 && sheets[j].x2 <=
cur.x2)
                   { sheets[j].y1 = cur.y2; continue; }
                //check for intersections at corners
                //upper left corner
                if (sheets[j].x1 < cur.x1 && sheets[j].x2 > cur.x1 &&
sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 /*&& sheets[j].y2 <
cur.y2*/)
                   {
                    sheets[curTotal].x1 = cur.x1; sheets[curTotal].y1
= sheets[j].y1;
                    sheets[curTotal].x2 = sheets[j].x2; sheets
[curTotal].y2 = sheets[j].y2;
                    sheets[curTotal].c = sheets[j].c; sheets
[curTotal].v = true;
                    curTotal++;
                    sheets[j].x2 = cur.x1;
                    continue;
                   }
                //upper right corner
                if (sheets[j].x2 > cur.x2 && sheets[j].x1 < cur.x2 &&
sheets[j].y1 < cur.y1 && sheets[j].y2 > cur.y1 /*&& sheets[j].y2 <
cur.y2*/)