• <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
            神啊原諒我吧我很菜!
            看了樹(shù)狀數(shù)組還沒(méi)思路!
            代碼ac后更新
            posted on 2009-01-10 10:24 KNIGHT 閱讀(177) 評(píng)論(1)  編輯 收藏 引用

            FeedBack:
            # re: Stars[未登錄](méi)
            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來(lái)了,但是他說(shuō)他也不會(huì)他是線(xiàn)段樹(shù)過(guò)的。。。。。
            線(xiàn)段樹(shù)。。。。。代碼不是我的。。。網(wǎng)上的。。。。不過(guò)不錯(cuò)。。。題目有個(gè)條件就是按y升序給出數(shù)據(jù)。。。。所以可以用樹(shù)狀數(shù)組,其實(shí)可以排序在用的。。。。。繼續(xù)物理。。。。關(guān)機(jī)。。。  回復(fù)  更多評(píng)論
              

            只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            <2009年2月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            1234567

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            亚洲一区二区三区日本久久九| 久久精品免费大片国产大片| 亚洲乱码精品久久久久..| 久久久久久久亚洲Av无码| 久久精品九九亚洲精品天堂 | 久久综合久久自在自线精品自 | 精品久久久久久久久久中文字幕| 久久久久久国产精品无码下载| 亚洲AV日韩AV永久无码久久| 国产精品福利一区二区久久| 一级做a爰片久久毛片看看| 国产人久久人人人人爽| 一级做a爱片久久毛片| 噜噜噜色噜噜噜久久| 亚洲国产成人久久精品影视| 亚洲精品无码久久一线| 欧美久久久久久精选9999| 国产精品国色综合久久| 久久综合久久综合亚洲| 国产巨作麻豆欧美亚洲综合久久 | 女人高潮久久久叫人喷水| 99久久精品国产一区二区三区 | 四虎国产精品成人免费久久| 久久精品国产精品青草app| 久久夜色精品国产噜噜亚洲AV| 久久久久一级精品亚洲国产成人综合AV区| 欧美va久久久噜噜噜久久| 久久无码高潮喷水| 97精品伊人久久大香线蕉| 一本久久a久久精品综合香蕉| 久久久91人妻无码精品蜜桃HD| 久久99免费视频| 97久久国产亚洲精品超碰热| 久久综合给久久狠狠97色 | 亚洲国产成人久久精品动漫| 久久国产精品国语对白| 久久久噜噜噜www成人网| 亚洲国产精品无码久久| 久久精品国产男包| 久久天天躁狠狠躁夜夜不卡| 国产韩国精品一区二区三区久久|