Hi, I got AC with N*N*logN too, but there's a beautiful Algo with recursive...
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;
}
