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

ACM___________________________

______________白白の屋
posts - 182, comments - 102, trackbacks - 0, articles - 0
<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

常用鏈接

留言簿(24)

隨筆分類(332)

隨筆檔案(182)

FRIENDS

搜索

積分與排名

最新隨筆

最新評論

閱讀排行榜

評論排行榜


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

 

題目地址:

 http://acm.hdu.edu.cn/showproblem.php?pid=2795

題目描述:

Billboard

Time Limit: 20000/8000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 733    Accepted Submission(s): 340


Problem Description
At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.

On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.

Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.

When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one.

If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university).

Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.
 

Input
There are multiple cases (no more than 40 cases).

The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements.

Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.
 

Output
For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can't be put on the billboard, output "-1" for this announcement.
 

Sample Input
3 5 5 2 4 3 3 3
 

Sample Output
1 2 1 3 -1
 

 

一開始沒想明白怎么做 ,  仔細想了想,   再次 讀題后 發現 , n <= 200000;  也就是說  最多 也就 200000 條廣告 , 你就算每行貼一張 ,

最多也就貼到 200000 行,  所以  不要被  h <= 10^9  次方嚇到了  ,認為 線段樹開不了那么大的數組  . 只要開 200000 就可以了 .

 

其他的 沒什么 好說的 , 知道這個 就直接 暴 吧 ............將近 7000MS .=水過.................   g++提交 還華麗的 送出了 一次 TLE....

C++  水過了 ............

 

//    一直沒明白 為什么我的 代碼速度 那么 慢,  查詢后 更新 的時間是 2000MS 左右  , 我的 是 查詢 就更新了,

竟然要 將近 7000MS ? 非常 郁悶 ,  不信邪的 繼續 檢查 代碼, 在 瞪了 1哥小時后 , 忽然想到 : 把 cout 改成

printf 會怎樣?   結果 :  1640 MS  AC ..............鬼知道他的 數據量有多大..... cout 和 printf

竟然 差了 5000 MS 的時間 ...........無語

代碼如下 :

 

 /*

Coded By  : MiYu

Link      : http://www.cnblogs.com/MiYu  || http://www.shnenglu.com/MiYu

Author By : MiYu

Test      : 1

Program   : 2795

*/

//#pragma warning( disable:4789 )

#include <iostream>

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

using namespace std;


struct ADV {

       int left, right, val;

       int mid () { return ( left + right ) >> 1; }     

}adv[800000];

int N, W, H, w;

void creat ( int l, int r, int rt = 1 ){

     adv[rt].left = l;

     adv[rt].right = r;

     adv[rt].val = W;

     if ( l == r )

        return ;

     int mid = adv[rt].mid();

     creat ( l, mid, rt << 1 );

     creat ( mid + 1, r, ( rt << 1 ) + 1 );

}

void add ( int rt = 1, int wei = w ){

    if ( wei <= adv[rt].val ){

         if ( adv[rt].left == adv[rt].right ){

              adv[rt].val -= wei;

              //cout << adv[rt].left << endl;  //杯具的 地方

printf ( "%d\n", adv[rt].left ); 

              return ;     

         } else if ( adv[rt<<1].val >= wei ) {

                add ( rt << 1 );

                adv[rt].val = max ( adv[rt<<1].val, adv[(rt<<1)+1].val );     

         } else {

                add ( ( rt << 1 ) + 1 );

                adv[rt].val = max ( adv[rt<<1].val, adv[(rt<<1)+1].val );        

         }   

    } else {

           //cout << -1 << endl;      //杯具的地方

puts ( "-1" );   

    }   

}

inline bool scan_ud(int &num)

{

    char in;

    in=getchar();

    if(in==EOF) return false;

    while(in<'0'||in>'9') in=getchar();

    num=in-'0';

    while(in=getchar(),in>='0'&&in<='9'){

        num*=10,num+=in-'0';

    }

    return true;

}

int main ()

{

    while ( scan_ud (H)&&scan_ud (W)&&scan_ud (N) ) {

           if ( H > 200000 )

               H = 200010;

           creat ( 1, H );

           for ( int i = 1; i <= N; ++ i ) {

                scan_ud (w);

                add ( );     

           }      

    }

    return 0;

}

 

 

 

 

另 附上 傻崽  神牛 代碼 :

 

#include <iostream>

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

#define FF(i,a) for( int i = 0 ; i < a ; i ++ )

#define FOR(i,a,b) for( int i = a ; i < b ; i ++ )

#define LL(a) a<<1

#define RR(a) a<<1|1

template<class T> inline void checkmin(T &a,T b) {if(a < 0 || a > b)a = b;}

template<class T> inline void checkmax(T &a,T b) {if(a < b) a = b;}

using namespace std;

struct Node {

int val;

int idx;

friend bool operator < (Node a , Node b) {

if(a.val == b.val) {

return a.idx > b.idx;

}

return a.val < b.val;

}

}error;

 

struct Seg_Tree{

int left,right;

Node node;

int mid() {

return (left + right)>>1;

}

}tt[800000];

 

int n , h , m;

 

void build(int l,int r,int idx) {

tt[idx].left = l;

tt[idx].right = r;

tt[idx].node.idx = l;

tt[idx].node.val = h;

if(l == r) return ;

int mid = tt[idx].mid();

build(l,mid,LL(idx));

build(mid+1,r,RR(idx));

}

 

void update(int l,int r,int val,int idx) {

if(l <= tt[idx].left && r >= tt[idx].right) {

tt[idx].node.val += val;

return ;

}

int mid = tt[idx].mid();

if(l <= mid) update(l,r,val,LL(idx));

if(mid < r) update(l,r,val,RR(idx));

tt[idx].node = max(tt[LL(idx)].node,tt[RR(idx)].node);

}

 

Node query(int w,int idx) {

if(tt[idx].node.val < w) {

return error;

}

if(tt[idx].left == tt[idx].right) {

return tt[idx].node;

}

if(tt[LL(idx)].node.val >= w) {

return query(w,LL(idx));

} else {

return query(w,RR(idx));

}

}

 

int main() {

error.idx = -1;

while(scanf("%d%d%d",&n,&h,&m) == 3) {

checkmin(n,m);

build(1,n,1);

while(m --) {

int w;

scanf("%d",&w);

Node ret = query(w,1);

printf("%d\n",ret.idx);

if(ret.idx != -1) {

update(ret.idx,ret.idx,-w,1);

}

}

}

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>
            亚洲欧美成人综合| 亚洲欧美日韩成人| 嫩草伊人久久精品少妇av杨幂| 国产亚洲精品aa午夜观看| 欧美一区二区私人影院日本| 欧美伊人影院| 亚洲国产精品一区二区尤物区| 亚洲国产成人av好男人在线观看| 欧美大片免费观看| 亚洲亚洲精品三区日韩精品在线视频 | 国产精品亚洲视频| 久久精品欧美日韩| 免费成人性网站| 亚洲性图久久| 久久九九精品99国产精品| 亚洲人成网站在线播| 亚洲午夜精品久久久久久app| 国产午夜精品一区理论片飘花| 免费视频一区| 国产精品久久久久久久第一福利| 久久婷婷久久一区二区三区| 欧美理论片在线观看| 欧美一区亚洲二区| 欧美国产日韩视频| 久久成人精品一区二区三区| 免费影视亚洲| 久久精品30| 欧美日韩中文字幕| 欧美成人一区在线| 国产日韩精品一区二区三区在线| 亚洲国产日韩在线| 国产一区再线| 99热精品在线观看| 亚洲黄色av一区| 欧美亚洲免费电影| 亚洲欧美国产一区二区三区| 麻豆久久精品| 久久午夜电影| 国产区亚洲区欧美区| 日韩午夜激情| 亚洲另类黄色| 另类亚洲自拍| 久久综合给合| 国产一区二区精品久久91| 一区二区国产在线观看| 日韩亚洲欧美中文三级| 久久香蕉精品| 美日韩精品视频| 国产一区二区三区自拍| 亚洲主播在线播放| 亚洲在线视频一区| 国产精品v欧美精品∨日韩| 91久久精品国产91久久性色tv| 激情久久综艺| 久久久久91| 蜜臀av一级做a爰片久久| 国外视频精品毛片| 久久国产日本精品| 久久免费黄色| 黄页网站一区| 久久综合网络一区二区| 免费成人小视频| 亚洲国内自拍| 欧美激情精品久久久久久免费印度| 欧美二区在线播放| 亚洲日本激情| 欧美国产日韩免费| 亚洲美女视频| 午夜日韩激情| 国产一区二区三区在线观看免费| 欧美一区激情| 欧美激情视频在线播放| 亚洲免费大片| 欧美网站在线| 欧美一区二区三区婷婷月色| 久久在线免费观看视频| 亚洲高清免费在线| 欧美精品日韩综合在线| 亚洲四色影视在线观看| 久久国产精品亚洲77777| 伊人精品久久久久7777| 欧美va亚洲va香蕉在线| 日韩一区二区高清| 欧美在线一二三区| 亚洲国产精品女人久久久| 欧美日韩精品一区二区天天拍小说 | 最新精品在线| 欧美一区二区视频在线观看2020| 国产综合视频| 欧美激情综合网| 亚洲永久免费av| 欧美a级片网| 亚洲午夜国产成人av电影男同| 国产欧美精品一区二区三区介绍| 久久免费精品日本久久中文字幕| 亚洲高清电影| 欧美影院在线| 一本色道久久| 激情文学综合丁香| 欧美调教视频| 噜噜噜噜噜久久久久久91| 亚洲色图制服丝袜| 欧美成人免费网| 欧美一区二区在线视频| 亚洲欧洲一级| 国产欧美日韩另类视频免费观看| 快播亚洲色图| 午夜精品999| 亚洲靠逼com| 欧美成人午夜免费视在线看片 | 有码中文亚洲精品| 国产精品v欧美精品∨日韩| 久久夜色精品国产| 欧美一区二区观看视频| 日韩一区二区免费高清| 欧美sm视频| 久久人人97超碰国产公开结果| 亚洲视频一区二区| 亚洲欧洲精品天堂一级| 国产一级一区二区| 国产精品欧美一区二区三区奶水 | 国产欧美一区二区精品仙草咪 | 欧美香蕉大胸在线视频观看| 久久精品日韩欧美| 亚洲国产精品久久久久秋霞不卡| 久久精品国产免费观看| 亚洲一区二区成人| 日韩一区二区高清| 亚洲国产三级网| 在线观看精品视频| 韩国成人精品a∨在线观看| 国产精品一二| 国产伦精品一区| 国产精品日韩二区| 国产精品高清在线观看| 欧美午夜欧美| 国产精品chinese| 国产精品xvideos88| 欧美激情一区二区三区不卡| 欧美高清在线播放| 欧美刺激性大交免费视频| 免费久久精品视频| 欧美黄色免费| 欧美金8天国| 欧美精品三级日韩久久| 欧美久久电影| 欧美午夜视频在线观看| 国产精品久久久久9999吃药| 国产精品一区二区三区成人| 国产欧美日韩亚州综合| 国语自产精品视频在线看| 在线不卡亚洲| 亚洲精品自在久久| 亚洲自拍偷拍视频| 欧美亚洲网站| 老色鬼精品视频在线观看播放| 欧美二区在线观看| 日韩一级免费观看| 亚洲欧洲av一区二区| 久久婷婷蜜乳一本欲蜜臀| 欧美韩国在线| 国产精品无码专区在线观看| 国内外成人免费视频| 亚洲人成在线影院| 亚洲一区二区在线播放| 久久久蜜桃精品| 亚洲国产精品一区在线观看不卡 | 午夜精品久久久久久久99水蜜桃 | 一区二区三区国产精品| 午夜国产精品影院在线观看| 久久蜜臀精品av| 亚洲日韩欧美视频一区| 亚洲欧美日产图| 欧美国产日韩一区二区三区| 欧美日韩另类综合| 精品88久久久久88久久久| 99精品视频免费| 久久最新视频| 亚洲性人人天天夜夜摸| 老司机午夜精品视频| 国产精品久久久久91| 亚洲国产日韩美| 午夜视频在线观看一区二区三区| 猛男gaygay欧美视频| 亚洲一区二区三区四区五区午夜 | 欧美一区二区三区的| 欧美日韩精选| 亚洲二区视频在线| 欧美一级片一区| 日韩一区二区精品视频| 久久综合激情| 国产亚洲美州欧州综合国| 99精品视频一区二区三区| 免费亚洲电影在线| 亚洲欧美国内爽妇网| 欧美日韩视频在线一区二区观看视频 | 亚洲国产成人久久综合| 欧美亚洲免费| 在线综合亚洲欧美在线视频| 欧美超级免费视 在线|