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

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(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;
            }
            

             

            久久精品国产精品亚洲艾草网美妙 | 国内精品久久久久久久97牛牛| 久久男人AV资源网站| 亚洲欧美日韩精品久久| 国产午夜精品久久久久九九电影 | 无夜精品久久久久久| 少妇高潮惨叫久久久久久| 精品一区二区久久| 亚洲国产精品无码久久九九| 精品蜜臀久久久久99网站| 久久精品亚洲乱码伦伦中文| 亚洲AV无码久久寂寞少妇| 国产亚洲精午夜久久久久久| 色8久久人人97超碰香蕉987| 久久久黄片| 91精品国产高清久久久久久国产嫩草 | 国产精品一区二区久久国产| 欧美成a人片免费看久久| 精品久久777| 久久亚洲私人国产精品vA | 97久久超碰国产精品旧版| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 国产精品丝袜久久久久久不卡| 中文字幕久久精品无码| 色综合久久中文字幕综合网| 久久r热这里有精品视频| 久久精品99久久香蕉国产色戒| 色综合久久久久综合99| 日韩美女18网站久久精品| 久久国产精品波多野结衣AV| 伊人久久免费视频| 人人狠狠综合久久亚洲婷婷| 久久精品成人| 91精品国产91久久久久久青草| 国产精品久久久久影院嫩草| 精品国产VA久久久久久久冰 | 久久91这里精品国产2020| 久久伊人精品青青草原高清| 97久久香蕉国产线看观看| 国产午夜福利精品久久2021| 国产精品毛片久久久久久久 |