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

             

            精品久久久久久99人妻| 久久精品国产亚洲AV忘忧草18| 久久久久久久久无码精品亚洲日韩 | 武侠古典久久婷婷狼人伊人| 精品久久久一二三区| 天天躁日日躁狠狠久久| 久久精品国产亚洲麻豆| 亚洲美日韩Av中文字幕无码久久久妻妇| 久久婷婷五月综合97色直播| 久久国产精品-国产精品| 亚洲色欲久久久久综合网| 天堂久久天堂AV色综合| 国产精品久久久久一区二区三区| 一本色道久久HEZYO无码| 国产高潮国产高潮久久久91 | 老色鬼久久亚洲AV综合| 久久国产香蕉一区精品| 久久精品水蜜桃av综合天堂| 亚洲国产精品成人久久蜜臀| 久久福利青草精品资源站| 麻豆av久久av盛宴av| 97久久精品人人做人人爽| 亚洲AV成人无码久久精品老人 | 乱亲女H秽乱长久久久| 少妇久久久久久被弄到高潮| 青青草原综合久久| 久久婷婷激情综合色综合俺也去| 无码人妻久久一区二区三区蜜桃| 人人狠狠综合久久亚洲88| 九九久久自然熟的香蕉图片| 一本色道久久综合狠狠躁| 99久久做夜夜爱天天做精品| 无码国内精品久久人妻麻豆按摩| 久久精品国产一区二区三区不卡| 人人狠狠综合久久亚洲88| 青青青国产精品国产精品久久久久| 国产精品无码久久久久久| 精品久久久久久成人AV| www性久久久com| 国产精品成人久久久久三级午夜电影| 久久综合九色综合久99 |