xfstart07
Get busy living or get busy dying

#include < iostream >

 
using   namespace  std;

 
 
struct  arr{

     
int  x,y;

 }a[
1000010 ];

 
int  t;

 
int  n,m,l;

 
long   long  MAX;

 
int  c[ 1010 ];
 
int  cmp( const   void *  no1, const   void *  no2){
     arr 
* nox = (arr * )no1, * noy = (arr * )no2;

     
if (nox -> x != noy -> x)  return  nox -> x - noy -> x;

     
else   return  nox -> y - noy -> y;

 }

 
int  lowbit( int  x){

     
return  x ^ (x & (x - 1 ));

 }

 
int  getsum( int  x){

     
int  sum = 0 ;

     
while (x){

         sum
+= c[x];

         x
-= lowbit(x);

     }

     
return  sum;

 }

 
void  modify( int  x){

     
while (x <= m){

         c[x]
++ ;

         x
+= lowbit(x);

     }

 }

 
int  main()

 {

     scanf(
" %d " , & t);

     
for ( int  ti = 1 ;ti <= t; ++ ti){

         scanf(
" %d%d%d " , & n, & m, & l);

         
for ( int  i = 0 ;i < l; ++ i)

             scanf(
" %d%d " , & a[i].x, & a[i].y);

         qsort(a,l,
sizeof (arr),cmp);

         
for ( int  i = 0 ;i <= m; ++ i) c[i] = 0 ;

         MAX
= 0 ;

         
for ( int  i = 0 ;i < l; ++ i){

             MAX
+= getsum(m) - getsum(a[i].y);

             modify(a[i].y);

         }

         printf(
" Test case %d: %lld\n " ,ti,MAX);

     }

     
return   0 ;

 }



posted on 2009-05-29 23:46 xfstart07 阅读(129) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理