• <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
            Minimizing maximizer
            Time Limit: 5000MS Memory Limit: 30000K
            Total Submissions: 1004 Accepted: 280

            Description
            The company Chris Ltd. is preparing a new sorting hardware called Maximizer. Maximizer has n inputs numbered from 1 to n. Each input represents one integer. Maximizer has one output which represents the maximum value present on Maximizer's inputs.

            Maximizer is implemented as a pipeline of sorters Sorter(i1, j1), ... , Sorter(ik, jk). Each sorter has n inputs and n outputs. Sorter(i, j) sorts values on inputs i, i+1,... , j in non-decreasing order and lets the other inputs pass through unchanged. The n-th output of the last sorter is the output of the Maximizer.

            An intern (a former ACM contestant) observed that some sorters could be excluded from the pipeline and Maximizer would still produce the correct result. What is the length of the shortest subsequence of the given sequence of sorters in the pipeline still producing correct results for all possible combinations of input values?

            Task
            Write a program that:

            reads a description of a Maximizer, i.e. the initial sequence of sorters in the pipeline,
            computes the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible input data,
            writes the result.

            Input
            The first line of the input contains two integers n and m (2 <= n <= 50000, 1 <= m <= 500000) separated by a single space. Integer n is the number of inputs and integer m is the number of sorters in the pipeline. The initial sequence of sorters is described in the next m lines. The k-th of these lines contains the parameters of the k-th sorter: two integers ik and jk (1 <= ik < jk <= n) separated by a single space.

            Output
            The output consists of only one line containing an integer equal to the length of the shortest subsequence of the initial sequence of sorters still producing correct results for all possible data.

            Sample Input

            40 6
            20 30
            1 10
            10 20
            20 30
            15 25
            30 40
            

             

            Sample Output

            4
            

             

            Hint
            Huge input data, scanf is recommended.

            Source
            Central Europe 2003

            //pku1769
            /*
             * trival DP dp[i] = dp[j] + 1 (if there is a segment starting from a->i && a <= j)  o(n^2)
             * 考慮到轉移的時候選擇的是一段內的最小dp值,運用點樹可以解決
             */
            #include <string.h>
            #include <stdio.h>

            const int N = 50010;
            const int MAXINT = 1000000000;

            int n, l;

            struct ST {int i,j,m,l,r,c;} st[2*N];
            int up, cnt;

            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 = MAXINT;
             if(x < y) {
              st[d].l = ++up; bd(up, x, st[d].m);
              st[d].r = ++up; bd(up, st[d].m+1, y);
             }
            }

            void ins(int d, int x, int c) {
             if(c < st[d].c)
              st[d].c = c;
             if(st[d].i != st[d].j) {
              if(x <= st[d].m)
               ins(st[d].l, x, c);
              else
               ins(st[d].r, x, c);
             }
            }

            int getmin(int d, int x, int y) {
             if(x <= st[d].i && y >= st[d].j)
              return st[d].c;
             int min = MAXINT;
             if(x <= st[d].m) {
              int now = getmin(st[d].l, x, y);
              if(now < min) min = now;
             }
             if(y > st[d].m) {
              int now = getmin(st[d].r, x, y);
              if(now < min) min = now;
             }
             return min;
            }

            int main() {
             int i, a, b;
             up = 0;
             scanf("%d %d ", &l, &n);
             bd(0, 1, l);
             ins(0, 1, 0);
             int max = 0;
             for(i = 0; i < n; ++i) {
              scanf("%d%d", &a, &b);
              if(a < b) {
               int min = getmin(0, a, b-1);
               ins(0, b, min+1);
              }
             }
             printf("%d\n", getmin(0, l, l));
             return 0;
            }

            Feedback

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2007-12-04 16:33 by je
            題目沒看懂,能解釋下么?

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2007-12-05 11:47 by oyjpart
            給定一個線段集,要求選擇其中一個最小的子集來覆蓋整個區域。
            要求選定的子集是按照題目給的序來覆蓋。

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-01-18 08:46 by Littleye
            很多測試好像得不到正確答案,例如:
            40 4
            10 30
            14 29
            25 30
            30 40
            答案應該是2,你的程序給的是1000000000(你的初始值)
            類似的例子還有不少

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-01-18 12:40 by oyjpart
            你的樣例是無解的,沒有線段覆蓋【0,10】的區間。

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-01-19 02:33 by Littleye
            I understand now. I don't think I understood the problem thoroughly before. Although the problem description doesn't clearly indicate that all the segments given should cover the whole segment(1,N), it is the right situation or else we can't get the right output from the maximizer. Now the problem description says that we can get the right output, so the subsequences given must cover the whole segments. Thanks a lot!

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-01-19 12:34 by oyjpart
            you are welcome

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-04-18 10:44 by l-y-p
            向大牛學習學習,“運用點樹可以解決”,好思想,很好很強大。但是還有一個疑點:在DP的時候應該從小到大進行,但是沒發現你對y坐標進行排序就直接進行,那如果是考慮這樣兩組數據:
            10 40
            0 10
            從10到40先確定到40的DP值為maxint+1,然后再由0~10確定10的值為1,這樣是不是有問題??你的程序我沒調試過,不曉得你是怎么處理的?

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-04-18 10:58 by l-y-p
            果然啊,剛調試了下,直接運行數據:
            40 2
            10 40
            0 10
            結果是1000000000,不知道是我沒看清楚還是程序的bug?

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-04-18 12:19 by oyjpart
            題目是有這樣的要求的:
            要求選定的子集是按照題目給的序來覆蓋。
            嘿嘿 如果我沒有理解錯你的意思的話

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2008-04-18 22:02 by l-y-p
            汗!
            What is the length of the shortest subsequence of the given sequence of sorters
            把排序一去掉就AC了,多謝大牛指點,呵呵。
            最先還一直在想如果可以排序的話就用不著用點樹了,直接貪心!

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2009-08-25 10:39 by demo
            你的程序過不了zoj 2451

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2009-09-07 23:58 by oyjpart
            題目是一樣的嗎

            # re: pku1769 新寫的線段樹(點樹)模版  回復  更多評論   

            2010-12-01 20:36 by LSK
            請仔細讀題。。。ZJU哪個是multi case的
            成人午夜精品无码区久久| 人妻久久久一区二区三区| 国产成人综合久久精品尤物| 久久se精品一区精品二区国产| 久久精品亚洲男人的天堂| 亚洲欧洲久久久精品| 午夜精品久久久久久99热| 国产精品免费久久| 久久影视国产亚洲| 久久精品国产亚洲精品| 久久99国内精品自在现线| 97r久久精品国产99国产精| 久久久久国色AV免费观看| 亚洲狠狠婷婷综合久久蜜芽| 国产精品成人无码久久久久久| 久久99精品国产99久久| 色天使久久综合网天天| 99精品国产免费久久久久久下载| 国产成人久久精品一区二区三区| 久久亚洲精品国产精品| 久久精品国产99国产精品澳门| 人人狠狠综合久久88成人| 久久精品国产男包| 久久99国产精品成人欧美| 久久国产精品一区| 99久久99这里只有免费费精品| 久久无码精品一区二区三区| 97久久超碰国产精品2021| 伊人久久大香线蕉综合Av| 色综合合久久天天给综看| 久久精品国产99国产精偷| 99久久精品午夜一区二区| 亚洲日韩中文无码久久| 欧美日韩精品久久免费| 久久国产综合精品五月天| 色综合久久中文色婷婷| 欧美一区二区精品久久| 久久夜色精品国产亚洲| 国产精品综合久久第一页| 成人亚洲欧美久久久久| 精品久久久久久国产免费了|