青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0
<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用鏈接

留言簿(24)

隨筆分類(332)

隨筆檔案(182)

FRIENDS

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜

MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋    

 

題目地址 :

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種操作可以同一個函數實現, 只需要傳一個標志量就行

3: 查詢可用區間

題目的數據意思 : 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)); // 線段的更新,  經典部分
     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;
}

 

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美视频日韩视频在线观看| 亚洲精品精选| 亚洲精品在线三区| 亚洲第一区色| 欧美v亚洲v综合ⅴ国产v| 在线视频成人| 欧美理论电影网| 99精品国产福利在线观看免费| 久久阴道视频| 亚洲另类自拍| 亚洲尤物在线视频观看| 国产一区美女| 亚洲第一天堂av| 国产精品第一区| 久久久精品动漫| 欧美大片在线看| 欧美在线免费观看| 欧美不卡视频| 久久国产福利| 欧美激情中文字幕在线| 欧美自拍偷拍午夜视频| 欧美承认网站| 久久精品一二三| 欧美日韩国产一区二区| 久久精品一区蜜桃臀影院 | 国产综合视频| 欧美国产乱视频| 国产精品videossex久久发布| 久久久久久久国产| 欧美日韩亚洲一区二区三区四区| 欧美在线视频在线播放完整版免费观看 | 久久午夜电影| 亚洲在线观看| 欧美激情视频在线播放| 久久精品在线观看| 欧美视频在线免费看| 欧美风情在线观看| 亚洲少妇诱惑| 亚洲一区在线观看视频| 久久久久国产一区二区三区| 一区二区三区鲁丝不卡| 久久精品综合网| 欧美一级欧美一级在线播放| 欧美丰满高潮xxxx喷水动漫| 久久精视频免费在线久久完整在线看| 欧美激情视频给我| 牛牛影视久久网| 国产一区二区日韩精品欧美精品| 亚洲人成毛片在线播放女女| 国产综合网站| 午夜精品网站| 亚洲欧美在线免费观看| 一区二区三区www| 久久一综合视频| 久久在线观看视频| 国产主播在线一区| 亚洲欧美成人一区二区在线电影| 一区二区av在线| 精品二区视频| 美日韩在线观看| 国产精品永久入口久久久| 亚洲激情午夜| 最新成人av网站| 欧美成人精精品一区二区频| 欧美高清日韩| 亚洲激情视频| 欧美顶级艳妇交换群宴| 亚洲日本成人网| 日韩亚洲一区在线播放| 欧美伦理在线观看| 日韩一级黄色大片| 亚洲男人av电影| 国产精品网红福利| 欧美一区免费| 美女视频黄 久久| 亚洲三级观看| 欧美日韩无遮挡| 亚洲先锋成人| 久久丁香综合五月国产三级网站| 美日韩在线观看| 亚洲高清视频在线观看| 日韩亚洲欧美中文三级| 欧美性大战久久久久久久蜜臀| 亚洲一区不卡| 久久综合免费视频影院| 亚洲精品久久久蜜桃| 欧美剧在线观看| 亚洲欧美日韩区| 免费看的黄色欧美网站| 9色精品在线| 国产精品入口麻豆原神| 久久精品一区蜜桃臀影院| 亚洲电影av| 亚洲自拍电影| 在线欧美一区| 美女精品在线| 亚洲一区二区三区在线播放| 国产日韩在线一区| 欧美激情亚洲国产| 亚洲欧美久久久久一区二区三区| 男女av一区三区二区色多| 欧美精品七区| 国产综合色精品一区二区三区| 性伦欧美刺激片在线观看| 男女激情视频一区| 亚洲宅男天堂在线观看无病毒| 国产一区二区无遮挡| 欧美精品aa| 久久精品国产精品亚洲综合| 日韩系列在线| 麻豆精品国产91久久久久久| 亚洲午夜在线观看视频在线| 在线观看成人网| 国产女人18毛片水18精品| 欧美黄色aaaa| 久久综合99re88久久爱| 亚洲性图久久| 99精品欧美一区二区三区综合在线| 久久久久成人精品| 欧美亚洲午夜视频在线观看| 日韩香蕉视频| 亚洲国产精品v| 国内外成人免费视频| 欧美三级视频在线播放| 欧美一区二区三区在线免费观看 | 久久久久久久网| 亚洲精品一区二区三区婷婷月| 久久久久在线观看| 亚洲欧美变态国产另类| 夜夜嗨av一区二区三区四区| 在线欧美电影| 黄色成人在线| 红桃视频一区| 影音国产精品| 国产主播一区二区三区四区| 国产日韩精品入口| 国产精品日韩一区| 国产伦精品一区二区三区免费| 欧美视频在线观看| 国产精品久久999| 国产精品国产三级国产专区53 | 欧美日韩一区在线视频| 亚洲影院色无极综合| 欧美激情aaaa| 榴莲视频成人在线观看| 久久成人免费日本黄色| 欧美一区二区视频网站| 欧美诱惑福利视频| 久久频这里精品99香蕉| 久久久久久久久久看片| 美国十次成人| 亚洲国产精品精华液2区45| 欧美黄色精品| 亚洲伦理一区| 亚洲欧美成人一区二区在线电影| 亚洲专区一区| 久久综合精品一区| 欧美成人一区二区| 欧美日韩视频在线一区二区观看视频| 欧美日韩精品三区| 国产精品私拍pans大尺度在线 | 久久免费视频一区| 欧美福利电影网| 欧美日韩中文字幕| 国产女人18毛片水18精品| 在线综合视频| 久久精品午夜| 亚洲日本欧美| 午夜精品成人在线| 每日更新成人在线视频| 欧美日韩一区二区三区视频 | 国产女人水真多18毛片18精品视频| 国产视频在线观看一区二区三区| 精品不卡视频| 国产精品99久久久久久白浆小说| 久久精品女人的天堂av| 亚洲国产欧美不卡在线观看| 中国av一区| 美女精品网站| 国产精品视频一区二区三区| 136国产福利精品导航网址应用 | 一本色道久久加勒比88综合| 新狼窝色av性久久久久久| 欧美chengren| 亚洲欧美日韩精品久久奇米色影视| 久久在线视频| 国产欧美视频一区二区三区| 99热精品在线| 牛人盗摄一区二区三区视频| 亚洲午夜在线| 欧美日韩成人一区二区| 一区二区三区亚洲| 欧美一区午夜视频在线观看| 最新国产乱人伦偷精品免费网站| 欧美一区二视频| 国产精品视频最多的网站| 一个人看的www久久| 欧美成人免费小视频| 亚洲激精日韩激精欧美精品| 亚洲欧美资源在线|