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;
}