posts - 16,comments - 0,trackbacks - 0
 1 # include <cstdio>
 2 # include <cstring>
 3 # include <algorithm>
 4 using namespace std;
 5 
 6 # define B 100005
 7 # define N 100005
 8 
 9 struct Intv {int s, e;};
10 
11 Intv c[N];
12 int n, a[B], r[N], le[N];
13 
14 bool cmp(const int x, const int y)
15 {
16                 if (c[x].s == c[y].s) return c[x].e > c[y].e;
17                 return c[x].s < c[y].s;
18 }
19 /**************************************************/
20 int getsum(int x)
21 {
22                 int ret = 0;
23                 while (x > 0) ret += a[x], x -= x&(-x);
24                 return ret;
25 }
26 void inc(int x)
27 {
28                 while (x <= B) ++a[x], x += x&(-x);
29 }
30 /**************************************************/
31 int main()
32 {
33                 int i, n, x;
34 
35                 while (scanf("%d"&n), n)
36                 {
37                                 memset(a, 0sizeof(a));
38                                 for (i = 0; i < n; ++i)
39                                                 r[i] = i, scanf("%d%d"&c[i].s, &c[i].e);
40                                 sort(r, r+n, cmp);
41                                 for (i = 0; i < n; ++i)
42                                 {
43                                                 x = c[r[i]].e + 1, inc(x);
44                                                 if (i && c[r[i]].e==c[r[i-1]].e && c[r[i]].s==c[r[i-1]].s)
45                                                                 le[r[i]] = le[r[i-1]];
46                                                 else
47                                                                 le[r[i]] = i-getsum(x-1);
48                                 }
49                                 for (i = 0; i < n; ++i)
50                                 {
51                                                 if (i) putchar(' ');
52                                                 printf("%d", le[i]);
53                                 }
54                                 putchar('\n');
55                 }
56 
57                 return 0;
58 }
59 
posted on 2012-09-02 11:51 yajunw 阅读(119) 评论(0)  编辑 收藏 引用

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