TOJ 2553 Japan

 1 /* 
 2  * File:   H.cpp
 3  * Author: GongZhi
 4  * Problem:
 5  * Created on 2009年7月27日, 上午9:41
 6  */
 7 
 8 #include <stdlib.h>
 9 #include <string.h>
10 #include <iostream>
11 #include <string>
12 #include <vector>
13 #include <map>
14 #include <queue>
15 #include <algorithm>
16 using namespace std;
17 const int MAX=1100;
18 struct node{
19     int x,y;
20 }data[MAX*MAX];
21 int n,m;
22 long long seg[MAX];
23 bool cmp(node a, node b)
24 {
25     return a.x<b.x||a.x==b.x&&a.y<b.y;
26 }
27 /*
28  *
29  */
30 int lowbit(int x)
31 {
32     return x^(x&(x-1));
33 }
34 
35 int add(int x,int d)
36 {
37     while(x<=m)
38     {
39         seg[x]+=d;
40         x+=lowbit(x);
41     }
42     return 0;
43 }
44 
45 long long sum(int x)
46 {
47     long long ans=0;
48     while(x>0)
49     {
50         ans+=seg[x];
51         x-=lowbit(x);
52     }
53     return ans;
54 }
55 
56 int main() {
57     int kase;
58     int k,l;
59     scanf("%d",&kase);
60     for(k=1;k<=kase;k++){
61         scanf("%d%d%d",&n,&m,&l);
62         for(int i=0;i<l;++i)
63             scanf("%d%d",&data[i].x,&data[i].y);
64         sort(data,data+l,cmp);
65         memset(seg,0,sizeof(seg));
66         long long ans=0;
67         for(int i=0;i<l;++i)
68         {
69             add(data[i].y,1);
70             ans+=sum(m)-sum(data[i].y);
71         }
72         printf("Test case %d: %lld\n",k,ans);
73     }
74     return 0;
75 }
76 

posted on 2009-07-27 16:00 gong 阅读(1122) 评论(1)  编辑 收藏 引用

评论

# re: TOJ 2553 Japan 2009-07-28 15:18 戴尔电脑

上看到家十分  回复  更多评论   


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


<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜