I think it's right, but WA :(

Comments at my program. Thanks in advance.


/*Here begins*/
#include<iostream.h>

#define MaxCol 2500

int A, B, N;
long col[MaxCol+1];

struct Line
{
    int  ly, uy, x, ind, col, sid;
}  *L;

/*Sort the vertical lines of the squares by x coordinate*/
void qsort(int l, int r)
{
  if (r <= l) return;
  int j = r;
  int i = (r+l)/2;
  Line x = L[i];
     L[i] = L[j];
  i = l;
     while (i < j)
     {
        while (i<j && L[i].x<=x.x) i++;
        L[j] = L[i];
        while (i<j && x.x<=L[j].x) j--;
        L[i] = L[j];
     }
  L[i] = x;
  qsort(l,j-1);
  qsort(i+1,r);
}

/*here come's the PriorityQueue implementation*/

Line *heap;
int  *map; /*map is used to map the lines to be removed in the heap*/
int  last;

void init()
{
    heap = new Line[N];
    map  = new  int[N];
}
void finit()
{
    delete[] heap;
    delete[] map;
}
/*swap Lines and the value map*/
void swap(Line& a, Line& b)
{
    int m;
    m = map[a.ind];
    map[a.ind] = map[b.ind];
    map[b.ind] = m;
    Line h;
    h = a;
    a = b;
    b = h;
}
void push(Line x)
{
    heap[++last] = x;
      map[x.ind] = last;
    int son = last;
    int dad = (son-1)/2;
    while (heap[son].ind > heap[dad].ind)
    {
        swap(heap[son], heap[dad]);
        son = dad;
        dad = (dad-1)/2;
    }
}
Line pop()
{
    int i = 0;
    Line first = heap[0];
        swap(heap[0], heap[last]);
        --last;
        while ( i*2 < last )
        {
            i = i*2 + 1;
                if ( i < last )
                    if ( heap[i+1].ind > heap[i].ind) i++;
            if ( heap[(i-1)/2].ind < heap[i].ind)
                  swap(heap[(i-1)/2], heap[i]);
        }
    return first;
}

void remove(Line x)
{
    int i = map[x.ind];
    swap(heap[i], heap[last]);
    --last;
    while ( i*2 < last )
    {
        i = i*2 + 1;
        if ( i < last )
            if ( heap[i+1].ind > heap[i].ind) i++;
        if ( heap[(i-1)/2].ind < heap[i].ind)
                swap(heap[(i-1)/2], heap[i]);
    }
}

void main()
{
int  lx, ly, ux, uy;
int  i, y, cut, c;
Line cur;
    cin >>A >>B >>N;
/* 2*N Lines */
    L = new Line[2*N];
    for (i=0; i<N; i++)
    {
        cin >>lx >>ly >>ux >>uy >>c;
        L[2*i].x = lx;
        L[2*i].ly = ly;
        L[2*i].uy = uy;
        L[2*i].sid= 0;
        L[2*i].ind= i;
        L[2*i].col= c;
/**/    L[2*i+1].x = ux;
        L[2*i+1].ly = ly;
        L[2*i+1].uy = uy;
        L[2*i+1].sid= 1;
        L[2*i+1].ind= i;
        L[2*i+1].col= c;
    }
    for (c=1; c<=MaxCol; c++)
        col[c] = 0;
    N *= 2;
    qsort(0, N-1);
/*Here begins all*/
    init();
    for (y=0; y<A; y++)
    {
        last = -1;
        cut = 0;
        for (i=0; i<N; i++)
            if (L[i].ly <=y && y<L[i].uy)
            {
/*If side is left side (0)*/
                if (L[i].sid==0)
                {
                    ++cut;
/*if it's the first left segment take it as a current*/
                    if (cut==1)
                    {
                        cur = L[i];
                        continue;
                    }
/*if the segment has a lower index push it*/
                    if (L[i].ind < cur.ind) push(L[i]);
/*if the segment has an higher index add length and take this last as
cur*/
                    if (L[i].ind > cur.ind)
                    {
                        col[cur.col]+=(L[i].x - cur.x);
                        push(cur);
                        cur = L[i];
                    }

Look at this test:
---------
5 5 32
1 0 3 2 2
3 1 3 1 2
0 0 2 1 1
1 4 4 5 2
0 1 1 5 1
4 4 5 4 1
3 2 5 5 1
2 1 3 1 1
4 1 5 2 2
0 0 3 5 1
3 1 5 4 2
0 4 4 4 2
1 5 4 5 1
1 0 5 2 2
0 4 2 5 2
2 1 2 2 2
4 0 5 4 2
3 1 5 2 2
4 1 4 2 2
1 1 4 5 1
2 3 2 5 2
0 2 3 2 2
2 3 3 4 1
2 4 5 4 2
1 0 2 5 1
0 1 4 5 2
1 2 4 3 2
0 1 5 1 1
3 0 4 3 1
2 0 3 3 1
1 1 2 4 1
2 2 2 4 1
---------
The picture is:
---------
1 2 2 2 2
1 1 1 1 2
1 1 1 2 2
1 1 1 2 2
2 2 2 2 1
---------
Correct answer is:
----
1 12
2 13
----
Your program answer is:
---
1 13
2 12
---
So, you program have a bug. I coudn't find test with less rectangles,
I think that bug is in your heap implementation.

Good Luck!

Actually i think my program it's ok, but got WA :|, do you know how
can i improve speed, it's supposed to be ANlogN.
Thanks in advance :)

> Look at this test:
> ---------
> 5 5 32
> 1 0 3 2 2
> 3 1 3 1 2
> 0 0 2 1 1
> 1 4 4 5 2
> 0 1 1 5 1
> 4 4 5 4 1
> 3 2 5 5 1
> 2 1 3 1 1
> 4 1 5 2 2
> 0 0 3 5 1
> 3 1 5 4 2
> 0 4 4 4 2
> 1 5 4 5 1
> 1 0 5 2 2
> 0 4 2 5 2
> 2 1 2 2 2
> 4 0 5 4 2
> 3 1 5 2 2
> 4 1 4 2 2
> 1 1 4 5 1
> 2 3 2 5 2
> 0 2 3 2 2
> 2 3 3 4 1
> 2 4 5 4 2
> 1 0 2 5 1
> 0 1 4 5 2
> 1 2 4 3 2
> 0 1 5 1 1
> 3 0 4 3 1
> 2 0 3 3 1
> 1 1 2 4 1
> 2 2 2 4 1
> ---------
> The picture is:
> ---------
> 1 2 2 2 2
> 1 1 1 1 2
> 1 1 1 2 2
> 1 1 1 2 2
> 2 2 2 2 1
> ---------
> Correct answer is:
> ----
> 1 12
> 2 13
> ----
> Your program answer is:
> ---
> 1 13
> 2 12
> ---
> So, you program have a bug. I coudn't find test with less
rectangles,
> I think that bug is in your heap implementation.
>
> Good Luck!