• <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://www.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久久国语露脸精品国产| 日韩精品久久久久久| 婷婷综合久久中文字幕| 精品久久久久久国产免费了| 久久国产精品免费一区二区三区| 国产精品成人久久久久三级午夜电影 | 色婷婷综合久久久久中文一区二区| 色偷偷88888欧美精品久久久| 国产婷婷成人久久Av免费高清| 久久久久综合中文字幕 | 精品人妻伦九区久久AAA片69| 亚洲国产成人乱码精品女人久久久不卡| 久久精品国产亚洲AV蜜臀色欲| 激情伊人五月天久久综合| 国产高潮久久免费观看| 久久久久av无码免费网| 婷婷综合久久狠狠色99h| 亚洲欧洲久久av| 国内精品久久久久久久亚洲| 天天躁日日躁狠狠久久| 精品久久久久久久国产潘金莲| 国产L精品国产亚洲区久久| 久久国内免费视频| 国产69精品久久久久APP下载| 久久夜色tv网站| 2021少妇久久久久久久久久| 成人午夜精品无码区久久| 久久久久久精品免费免费自慰| 国产精品成人无码久久久久久 | 国产免费久久精品99久久| 亚洲精品乱码久久久久久中文字幕| 久久久久久A亚洲欧洲AV冫| 免费观看成人久久网免费观看| 久久精品国产亚洲AV忘忧草18| 久久只有这里有精品4| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 久久天天躁狠狠躁夜夜网站 | 久久亚洲国产午夜精品理论片| 久久精品无码午夜福利理论片| 国产精品女同久久久久电影院| 亚洲欧洲日产国码无码久久99|