• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 74,  comments - 33,  trackbacks - 0

            Description

            Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

            For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.

            You are to write a program that will count the amounts of the stars of each level on a given map.

            Input

            The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.

            Output

            The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.

            Sample Input

            5
            1 1
            5 1
            7 1
            3 3
            5 5

            Sample Output

            1
            2
            1
            1
            0
            神啊原諒我吧我很菜!
            看了樹狀數組還沒思路!
            代碼ac后更新
            posted on 2009-01-10 10:24 KNIGHT 閱讀(176) 評論(1)  編輯 收藏 引用

            FeedBack:
            # re: Stars[未登錄]
            2009-01-12 10:01 | Knight
            #include<stdio.h>
            #define SIZE1 32000
            #define SIZE2 15000
            int c[SIZE1],a[SIZE1],out[SIZE2],n;
            int lowbit(int k)
            {
            return k&(-k);
            }
            int sum(int k)
            {
            int ret=0;
            while(k>0)
            {
            ret+=c[k];
            k-=lowbit(k);
            }
            return ret;
            }
            void change(int pos,int delt)
            {
            while(pos<=SIZE1)
            {
            c[pos]+=delt;
            pos+=lowbit(pos);
            }
            }
            void init()
            {
            int i;
            int x,y;
            for(i=0;i<n;i++)
            {
            scanf("%d%d",&x,&y);
            x++;
            out[sum(x-1)+a[x]]++;
            change(x,1);
            a[x]++;
            }
            }
            int main()
            {
            int i;
            scanf("%d",&n);
            init();
            for(i=0;i<n;i++)
            printf("%d\n",out[i]);
            }
            pip來了,但是他說他也不會他是線段樹過的。。。。。
            線段樹。。。。。代碼不是我的。。。網上的。。。。不過不錯。。。題目有個條件就是按y升序給出數據。。。。所以可以用樹狀數組,其實可以排序在用的。。。。。繼續物理。。。。關機。。。  回復  更多評論
              
            <2009年1月>
            28293031123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品国产亚洲77777| 久久久久无码中| 99久久er这里只有精品18| 久久久久久久女国产乱让韩| 亚洲午夜久久久久妓女影院 | 亚洲国产成人久久精品动漫| 天堂久久天堂AV色综合| 91精品国产91久久久久福利| 99久久综合国产精品二区| 一本大道久久东京热无码AV| 久久电影网一区| 久久无码中文字幕东京热| 久久午夜电影网| 久久精品国产亚洲AV久| 久久99国产精品99久久| 久久精品国产99国产精品亚洲| 99久久99久久久精品齐齐| 人妻精品久久久久中文字幕| 国产产无码乱码精品久久鸭| 久久强奷乱码老熟女| 国产99久久精品一区二区| 久久频这里精品99香蕉久| 亚洲精品高清国产一久久| 久久夜色精品国产噜噜亚洲AV| 久久久久亚洲av综合波多野结衣| 久久久久久久尹人综合网亚洲| 久久青青草原精品国产| 性欧美大战久久久久久久| 99久久夜色精品国产网站| 93精91精品国产综合久久香蕉| 国产精品99久久久久久人| 亚洲国产精品一区二区久久hs| 久久精品中文字幕有码| 国产精品欧美久久久久无广告| 国产精品一区二区久久不卡| 色狠狠久久AV五月综合| 女人高潮久久久叫人喷水| 亚洲欧洲精品成人久久奇米网| 99久久国产亚洲综合精品| 久久久青草青青国产亚洲免观| 美女久久久久久|