• <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>

            ACM___________________________

            ______________白白の屋
            posts - 182, comments - 102, trackbacks - 0, articles - 0
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

            MiYu原創(chuàng), 轉(zhuǎn)帖請注明 : 轉(zhuǎn)載自 ______________白白の屋    

            題目地址 :

            http://poj.org/problem?id=2352

            題目描述:

            Stars
            Time Limit: 1000MSMemory Limit: 65536K
            Total Submissions: 14814Accepted: 6404

            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ù)組 解法傳送門 : http://www.cnblogs.com/MiYu/archive/2010/08/26/1808963.html 
            代碼如下 : 
            /*
            Mail to   : miyubai@gamil.com
            Link      : http://www.cnblogs.com/MiYu  || http://www.shnenglu.com/MiYu
            Author By : MiYu
            Test      : 1
            Complier  : g++ mingw32-3.4.2
            Program   : POJ_2352
            Doc Name  : Stars
            */
            //#pragma warning( disable:4789 )
            #include <iostream>
            #include <fstream>
            #include <sstream>
            #include <algorithm>
            #include <string>
            #include <set>
            #include <map>
            #include <utility>
            #include <queue>
            #include <stack>
            #include <list>
            #include <vector>
            #include <cstdio>
            #include <cstdlib>
            #include <cstring>
            #include <cmath>
            #include <ctime>
            using namespace std;
            struct P{
                   int x, y;
            }p[15010];
            int seg[100000];
            int NN = 32768, res[15010];
            int get ( int &n ) {
                int i = 1;
                while ( i < n ) i << 1;
                return i;    
            }
            void modify ( int &pos ) {
                 pos += NN;
                 seg[pos] ++;
                 while ( pos > 1 ) {
                       if ( ~pos & 1 ) seg[pos>>1] ++;
                       pos >>= 1;
                 }
            }
            int query ( int pos ) {
                 pos += NN;  
                 int sum = seg[pos];
                 while ( pos > 1 ) {
                        if ( pos & 1 ) {
                             sum += seg[pos>>1];  
                        }      
                        pos >>= 1;
                 }   
                 return sum;
            }
            int main ()
            {
                int N;
                while ( scanf ( "%d", &N ) == 1 ) {
                       int pos;
                       memset ( res, 0, sizeof ( res ) );
                       memset ( seg, 0, sizeof ( seg ) );
                       for ( int i = 0; i < N; ++ i ) {
                              scanf ( "%d%*d", &pos );
                              res[ query ( pos ) ] ++;
                              modify ( pos );   
                       }   
                       for ( int i = 0; i < N; ++ i ) {
                            printf ( "%d\n", res[i] );     
                       } 
                }
                return 0;
            }
            

             

            久久成人精品视频| 99久久综合国产精品免费| 精品久久一区二区| 久久精品成人免费观看97| 精品国产综合区久久久久久| 性做久久久久久免费观看| 无码人妻久久一区二区三区蜜桃| 久久久久女人精品毛片| 国产视频久久| 无码AV波多野结衣久久| 久久伊人精品青青草原日本| 青青草原精品99久久精品66| 久久免费精品视频| 精品久久久中文字幕人妻| 国产精品成人99久久久久 | .精品久久久麻豆国产精品| 伊人久久精品线影院| 一本色道久久综合狠狠躁| AA级片免费看视频久久| 色88久久久久高潮综合影院| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 99久久无码一区人妻a黑| 亚洲欧洲精品成人久久曰影片 | 久久久久国产精品嫩草影院| 狠狠久久综合| 精品久久久久久无码中文野结衣 | 色青青草原桃花久久综合| 欧美亚洲国产精品久久蜜芽| 久久久久亚洲精品天堂| 思思久久好好热精品国产| 久久久精品国产Sm最大网站| 99国产欧美精品久久久蜜芽| 人妻无码久久一区二区三区免费 | 国产精品久久久久久久久软件| 亚洲一区二区三区日本久久九| 国产精品99久久99久久久| 久久久久亚洲av无码专区喷水 | 久久综合综合久久97色| 91精品国产高清久久久久久io| 国产人久久人人人人爽| 国内精品久久久久久野外|