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

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            pku3667 hotel

            Posted on 2008-07-27 19:49 oyjpart 閱讀(2933) 評論(1)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Hotel

            Time Limit: 3000MS

             

            Memory Limit: 65536K

            Total Submissions: 478

             

            Accepted: 129

            Description

            The cows are journeying north to in 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 ≤ XiN-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 Di (b) Three space-separated integers representing a check-out: 2, Xi, and Di

            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

            Source

            USACO 2008 February Gold

             

             

            這是一個線段樹的題目:

             

            1.     題意建模:

            關鍵點:找出最靠左的一個長度至少為K的線段可以用線段樹來做。

            對任意一個線段樹中的節點(x,y) 維護3個信息:

            1.     (x, y) 中最長的線段的長度

            2.     x點開始向右的線段長度

            3.     y點開始向左的線段長度

            題目要求我們對一個(0, 50000)長的區間做以下操作:

            A.   對任意區間 (x, y) 使 F(x, y) = 0

            B.   對任意區間 (x, y) 使 F(x, y) = 1

            C.   查詢任意一個區間 (x, y) 中最長的線段的長度,

            D.   維護每個節點的3種信息

             

            2.難點解析:

                  1.實現A, B 操作:

            要把某個節點覆蓋為0,或者1,不需要向下擴展。只有在需要查詢到兒子區間的狀態的時候才需要擴展(參考spread函數)

            2.實現D的維護:

            每次改變了左右兒子區間的信息的時候,就需要更新當前節點的信息(參考update函數)

             

            3.代碼實現:

             

            #include <stdio.h>

             

            #define Max(a, b) ((a)>(b)?(a):(b))

             

            const int N = 50010;

             

            struct ST {int i,j,m,l,r,c,lc,rc;} st[2*N]; //区间宽度的2�

            int up, n;

             

            void bd(int d, int x, int y) {

                  st[d].i = x, st[d].j = y, st[d].m = (x+y)/2;

                  st[d].c = st[d].lc = st[d].rc = y-x;

                  if(x < y-1) {

                       st[d].l = ++up; bd(up, x, st[d].m);

                       st[d].r = ++up; bd(up, st[d].m, y);

                  }

            }

             

            void spread(int d) {

                  if(st[d].c == st[d].j-st[d].i) {

                       int& l = st[d].l, &r = st[d].r;

                       st[l].c = st[l].lc = st[l].rc = st[l].j-st[l].i;

                       st[r].c = st[r].lc = st[r].rc = st[r].j-st[r].i;

                  } else if(st[d].c == 0) {

                       int& l = st[d].l, &r = st[d].r;

                       st[l].c = st[l].lc = st[l].rc = 0;

                       st[r].c = st[r].lc = st[r].rc = 0;

                  }

            }

             

            void update(int d) {

                  st[d].c = Max(Max(st[st[d].l].c, st[st[d].r].c), st[st[d].l].rc + st[st[d].r].lc);

                  if(st[st[d].l].c == st[st[d].l].j-st[st[d].l].i) {

                       st[d].lc = st[st[d].l].c + st[st[d].r].lc;

                  } else st[d].lc = st[st[d].l].lc;

                  if(st[st[d].r].rc == st[st[d].r].j-st[st[d].r].i) {

                       st[d].rc = st[st[d].r].rc + st[st[d].l].rc;

                  } else st[d].rc = st[st[d].r].rc;

            }

             

            void Empty(int d, int x, int y) {

                  if(x <= st[d].i && y >= st[d].j) {

                       st[d].c = st[d].lc = st[d].rc = 0;

                       return;

                  }

             

                  spread(d);

             

                  if(x < st[d].m) Empty(st[d].l, x, y);

                  if(y > st[d].m) Empty(st[d].r, x, y);

             

                  update(d);

            }

             

            void Fill(int d, int x, int y) {

                  if(x <= st[d].i && y >= st[d].j) {

                       st[d].c = st[d].lc = st[d].rc = st[d].j-st[d].i;

                       return;

                  }

             

                  spread(d);

             

                  if(x < st[d].m) Fill(st[d].l, x, y);

                  if(y > st[d].m) Fill(st[d].r, x, y);

             

                  update(d);

            }

             

            int Get(int d, int l) {

                 

                  spread(d);

             

                  if(st[d].c < l) return -1;

                  if(st[st[d].l].c >= l)

                       return Get(st[d].l, l);

                  else if(st[st[d].l].rc + st[st[d].r].lc >= l) {

                       return st[st[d].l].j-st[st[d].l].rc;

                  }

                  return Get(st[d].r, l);

            }

             

            int main()

            {

                  int i, nq, cmd, x, l, y;

                  up = 0;

                  scanf("%d%d", &n, &nq);

                  bd(0, 0, n);

                  while(nq--) {

                       scanf("%d", &cmd);

                       if(cmd == 1) {

                             scanf("%d", &l);

                             x = Get(0, l);

                             if(x != -1)

                                  Empty(0, x, x+l);

                             printf("%d\n", x+1);

                       } else {

                             scanf("%d%d", &x, &l);

                             Fill(0, x-1, x+l-1);

                       }

                  }

                  return 0;

            }



            Feedback

            # re: pku3667 hotel  回復  更多評論   

            2008-09-26 10:59 by AngelClover
            還是大牛的思路比較清晰~
            精品伊人久久大线蕉色首页| 77777亚洲午夜久久多人| 亚洲国产精品久久电影欧美 | 国产aⅴ激情无码久久| 久久天堂AV综合合色蜜桃网| 国产精品久久一区二区三区| 91精品国产综合久久香蕉| 亚洲va久久久久| 久久发布国产伦子伦精品| 久久激情五月丁香伊人| 伊人久久综合成人网| 久久精品国产一区二区电影| 狠狠色狠狠色综合久久| 久久国产成人| 精品久久久久香蕉网| 综合久久精品色| 99国产欧美久久久精品蜜芽 | 久久久久久九九99精品| 久久天天躁狠狠躁夜夜2020老熟妇| 伊人久久大香线蕉av一区| 国产成人久久久精品二区三区| 色88久久久久高潮综合影院| 开心久久婷婷综合中文字幕| 久久精品国产91久久麻豆自制| 99精品久久久久久久婷婷| 久久久久久无码国产精品中文字幕| 97久久精品无码一区二区| 一本久久a久久精品亚洲| 一本久久免费视频| 久久人人爽人人爽人人片AV麻豆 | 国产A三级久久精品| 无码人妻少妇久久中文字幕| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | 无遮挡粉嫩小泬久久久久久久| 久久综合给合综合久久| 久久er国产精品免费观看8| 亚洲综合精品香蕉久久网97| 久久久久久亚洲AV无码专区| 久久综合给合久久国产免费| 亚洲AV日韩AV永久无码久久| 亚洲国产欧美国产综合久久|