?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,?0,?sizeof(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 閱讀(133)
評論(0) 編輯 收藏 引用