• <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
            <2010年9月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            常用鏈接

            留言簿(24)

            隨筆分類(332)

            隨筆檔案(182)

            FRIENDS

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            評論排行榜

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

             

            題目地址 :

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

            題目描述:

            Hotel
            Time Limit: 3000MSMemory Limit: 65536K
            Total Submissions: 2993Accepted: 1143

            Description

            The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake, of course).

            The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible.

            Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout.

            Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied.

            Input

            * Line 1: Two space-separated integers: N and M
            * Lines 2..M+1: Line i+1 contains request expressed as one of two possible formats: (a) Two space separated integers representing a check-in request: 1 and D(b) Three space-separated integers representing a check-out: 2, Xi, andDi

            Output

            * Lines 1.....: For each check-in request, output a single line with a single integer r, the first room in the contiguous sequence of rooms to be occupied. If the request cannot be satisfied, output 0.

            Sample Input

            10 6
            1 3
            1 3
            1 3
            1 3
            2 5 5
            1 6
            

            Sample Output

            1
            4
            7
            0
            5

             題目分析:

              題目打大意就是 找一段最左邊的滿足要求的線段.

            右下面幾種操作 :

            1: 插入線段

            2: 刪除線段

            上面2種操作可以同一個函數(shù)實現(xiàn), 只需要傳一個標志量就行

            3: 查詢可用區(qū)間

            題目的數(shù)據(jù)意思 : 1 3   表示 要申請最左邊的滿足要求的線段, 輸出線段的左端點, 同時更新線段樹,   沒有滿足要求的線段時輸出0 , 這時不要更新線段 !!! 這里WA幾次 杯具

                   2 5 5 表示 刪除以5為左端點, 長為5 的線段  , 就是 刪除[5,9].    

            具體請看 代碼注釋 :

             

            代碼
            /*
            Mail to   : miyubai@gamil.com
            Link      : 
            http://www.cnblogs.com/MiYu  || http://m.shnenglu.com/MiYu
            Author By : MiYu
            Test      : 1
            Complier  : g++ mingw32-3.4.2
            Program   : PKU_3667
            Doc Name  : HOTEL
            */
            //#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;
            inline 
            int max ( int a, int b ) {
                   
            return a > b ? a : b;       
            }
            struct segTree {
                   
            int left, right, lVal, rVal, mVal, cov;// cov -- >  0: 線段為空   1: 線段為滿  -1:2種情況都有 
                   int mid () { return (left+right)>>1; }
                   
            int dis () { return right - left + 1; }
                   
            void set ( int flag ) { // 0: 線段為空   1: 線段為滿 
                        if ( flag ){
                             cov 
            = 1;
                             lVal 
            = rVal = mVal = 0;  
                        } 
            else {
                             cov 
            = 0;
                             lVal 
            = rVal = mVal = right - left + 1;     
                        }
                   }     
            }seg[
            160000];
            void creat ( int left, int right, int rt = 1 ) {   // 初始化線段 
                 seg[rt].left = left;
                 seg[rt].right 
            = right;
                 seg[rt].
            set (0);
                 
            if ( left == right ) return;
                 
            int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();  
                 creat ( left, mid, LL );
                 creat ( mid 
            + 1, right, RR );  
            }
            void modify ( int left, int right, int flag, int rt = 1 ) {
                 
            if ( seg[rt].left >= left && seg[rt].right <= right ) {   //如果線段被覆蓋,  直接按flag標記處理,返回 
                     seg[rt].set ( flag );   return;
                 }     
                 
            int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
                 
            if ( seg[rt].cov != -1 ) {     // 如果線段不是混合情況(即線段是被覆蓋的), 把標志下傳 
                      seg[LL].cov = seg[RR].cov = seg[rt].cov;
                      seg[LL].
            set ( seg[LL].cov );   
                      seg[RR].
            set ( seg[RR].cov );
                 } 
                 
            if ( right <= mid ) modify ( left, right, flag, LL );    //遞歸更新線段 
                 else if ( left > mid ) modify ( left, right, flag, RR );
                 
            else {
                       modify ( left, mid, flag, LL );
                       modify ( mid 
            + 1, right, flag, RR );     
                 }
                 
            if ( seg[LL].cov == 0 && seg[RR].cov == 0 ) seg[rt].cov = 0//線段為空 
                 else if ( seg[LL].cov == 1 && seg[RR].cov == 1 ) seg[rt].cov = 1//線段滿 
                 else seg[rt].cov = -1;  // 2種情況都有 
                 seg[rt].mVal = max(seg[LL].rVal+seg[RR].lVal,max(seg[LL].mVal, seg[RR].mVal)); // 線段的更新,  經(jīng)典部分
                 seg[rt].lVal 
            = seg[LL].lVal + ( seg[LL].cov == 0 ? seg[RR].lVal : 0 );
                 seg[rt].rVal 
            = seg[RR].rVal + ( seg[RR].cov == 0 ? seg[LL].rVal : 0 );
            }
            int query ( int val, int rt = 1 ) {
                
            int LL = rt << 1, RR = rt << 1 | 1, mid = seg[rt].mid();
                
            if ( seg[rt].cov == 0 && seg[rt].mVal >= val ) {   //線段為空,且可用,直接返回線段左端點 
                         return seg[rt].left;
                } 
            else if ( seg[rt].cov == -1 ) {   //分三種 情況處理  左   左右    右  處理   
                     if ( seg[LL].mVal >= val ) return query ( val, LL );
                     
            else if ( seg[LL].rVal + seg[RR].lVal >= val ) return mid - seg[LL].rVal + 1;
                     
            else if ( seg[RR].mVal >= val )return query ( val, RR );  
                }   
                
            return 0;
            }
            int main ()
            {
                
            int N, M, left, right, val, choice;
                
            while ( scanf ( "%d%d"&N,&M ) == 2 ) {
                       creat ( 
            1, N );
                       
            while ( M -- ) {
                              scanf ( 
            "%d"&choice );
                              
            switch ( choice ) {
                                      
            case 1 : scanf ( "%d",&val );
                                               printf ( 
            "%d\n", left = query ( val ) );
                                               
            if ( left != 0 ) {
                                                    right 
            = left + val - 1;
                                                    modify ( left, right, 
            1 );
                                               }
                                               
            break;
                                      
            case 2 : scanf ( "%d%d",&left, &val );
                                               right 
            = left + val - 1;
                                               modify ( left, right, 
            0 );
                                               
            break;       
                              }       
                       }      
                }
                
            return 0;
            }

             

            亚洲国产精品久久久久网站| 超级碰碰碰碰97久久久久| 国产高潮国产高潮久久久91 | 国内精品久久久久久久coent | 久久精品国产亚洲av麻豆色欲| 久久人人爽人爽人人爽av| 大美女久久久久久j久久| 久久无码AV中文出轨人妻| 国产成人久久精品区一区二区| 久久精品国产亚洲AV久| 久久精品99无色码中文字幕| 久久精品成人免费国产片小草| 久久久无码精品亚洲日韩蜜臀浪潮 | 久久er热视频在这里精品| 成人资源影音先锋久久资源网| 伊人久久大香线蕉综合5g| 亚洲另类欧美综合久久图片区| 国内精品久久久久影院日本| 国产成年无码久久久久毛片| 亚洲欧美成人久久综合中文网| 久久这里只精品国产99热| 色8激情欧美成人久久综合电| 欧美久久久久久精选9999| 久久精品国产91久久综合麻豆自制| 伊人久久综合无码成人网| AAA级久久久精品无码片| 亚洲av成人无码久久精品| 久久777国产线看观看精品| 亚洲欧美伊人久久综合一区二区| 精品久久久久久无码不卡| 色综合久久中文字幕综合网| 久久久久久久久久免免费精品| 久久国产成人午夜aⅴ影院 | 亚洲国产日韩欧美综合久久| 亚洲色欲久久久久综合网| 亚洲精品NV久久久久久久久久| 青青青青久久精品国产h久久精品五福影院1421 | 久久综合亚洲色HEZYO国产| 中文字幕久久精品| 久久妇女高潮几次MBA| 国产成人精品免费久久久久|