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

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>
            久久久精品日韩| 一区二区高清视频| 另类国产ts人妖高潮视频| 亚洲在线免费视频| 国产视频亚洲| 欧美激情精品久久久久久大尺度 | 欧美日韩中文字幕精品| 亚洲免费视频成人| 久久国产一区二区| 亚洲精品久久久久久一区二区| 欧美多人爱爱视频网站| 欧美日韩亚洲高清一区二区| 羞羞色国产精品| 久久在线免费观看视频| 一区二区欧美视频| 欧美亚洲一级| 99视频在线观看一区三区| 亚洲一区激情| 亚洲国产精品成人精品 | 欧美一区二区免费观在线| 久久九九久久九九| 99精品免费| 欧美在线免费视屏| 日韩一级大片在线| 小辣椒精品导航| 一区二区三区精品视频| 欧美影院在线播放| 一区二区福利| 老色鬼精品视频在线观看播放| 亚洲深夜福利在线| 久久婷婷久久一区二区三区| 亚洲永久免费av| 欧美成人69| 久久久久久久久久久一区 | 性色av一区二区三区在线观看 | 最新成人av在线| 欧美一区日本一区韩国一区| 99re热这里只有精品免费视频| 羞羞色国产精品| 亚洲嫩草精品久久| 欧美伦理在线观看| 久久久噜噜噜久久久| 国产精品蜜臀在线观看| 亚洲激情在线观看| 国产一区视频在线观看免费| 夜夜嗨av一区二区三区网站四季av | 国产精品久久久久久久久久免费看| 欧美成人午夜激情在线| 国内久久视频| 午夜精品久久久久久久蜜桃app | 老司机久久99久久精品播放免费| 国产精品久久久久久久久久免费看 | 欧美在线欧美在线| 欧美丝袜第一区| 亚洲欧洲视频| 99国产精品久久久久老师| 老司机精品视频一区二区三区| 久久精品国产亚洲一区二区三区| 国产精品r级在线| 99精品国产在热久久婷婷| 亚洲第一网站| 久久久中精品2020中文| 久久综合色88| 国产一级一区二区| 久久国产精品第一页| 久久国内精品视频| 国自产拍偷拍福利精品免费一| 欧美亚洲免费电影| 久久爱www.| 国产欧美日韩三区| 欧美一区视频| 久久久久一区二区| 国产在线观看一区| 欧美一区二区三区在线观看| 久久偷看各类wc女厕嘘嘘偷窃| 国产婷婷色一区二区三区四区| 欧美一区二区三区四区在线| 免费欧美在线| 99re这里只有精品6| 欧美日韩亚洲在线| 亚洲一区在线观看免费观看电影高清| 亚洲欧美美女| 狠狠色狠狠色综合日日91app| 久久精品国产v日韩v亚洲| 免费看精品久久片| 夜夜精品视频| 国产日韩欧美一二三区| 久久影院午夜论| 一本色道久久综合亚洲精品高清 | 亚洲视频观看| 午夜精品久久久久久久久久久| 国产精品素人视频| 久久精品免费播放| 免费欧美日韩| 亚洲美女福利视频网站| 国产精品视频第一区| 久久综合九色综合久99| 亚洲日本欧美日韩高观看| 亚洲综合日韩在线| 韩日精品视频一区| 欧美精品在线免费播放| 亚洲欧美成人网| 欧美国产精品久久| 亚洲免费视频中文字幕| 国产一区二区欧美日韩| 欧美激情按摩| 久久国产天堂福利天堂| 亚洲精选一区| 麻豆成人在线观看| 亚洲欧美视频| 日韩视频在线观看免费| 国产亚洲精品资源在线26u| 欧美精品成人在线| 久久精品夜色噜噜亚洲a∨ | 99日韩精品| 黄色精品一二区| 欧美国产一区二区在线观看| 亚洲一区二区视频| 亚洲国产精品一区二区尤物区| 亚欧成人精品| 一区二区三区国产盗摄| 亚洲高清影视| 国产欧美日韩精品在线| 欧美三级韩国三级日本三斤| 欧美88av| 欧美电影在线观看完整版| 久久国产精品电影| 欧美一级片久久久久久久| 亚洲麻豆国产自偷在线| 你懂的视频欧美| 久久久www成人免费精品| 亚洲一区亚洲| aa级大片欧美| 日韩小视频在线观看| 亚洲电影毛片| 在线精品视频一区二区| 国产日本欧美视频| 国产精品视频导航| 国产精品剧情在线亚洲| 欧美视频一区二区三区| 欧美激情在线观看| 欧美理论大片| 欧美激情综合亚洲一二区| 午夜在线精品| 欧美一级电影久久| 欧美一区视频在线| 欧美在线观看一区二区| 久久国产福利| 久久久女女女女999久久| 久久久精品性| 久久午夜国产精品| 蜜桃av噜噜一区二区三区| 久久久综合网站| 噜噜噜躁狠狠躁狠狠精品视频| 久久亚洲国产精品日日av夜夜| 老巨人导航500精品| 欧美成人国产va精品日本一级| 免费高清在线一区| 亚洲尤物视频在线| 亚洲欧美影音先锋| 久久久国产精品一区二区三区| 久久日韩精品| 欧美黄色aa电影| 国产精品成人va在线观看| 国产亚洲精品一区二555| 亚洲福利视频网| 日韩午夜av| 午夜亚洲一区| 美女精品国产| 最新亚洲视频| 亚洲深夜福利视频| 欧美在线亚洲| 欧美激情综合色| 国产精品人人做人人爽| 国语自产精品视频在线看8查询8| 亚洲激情在线观看| 午夜日韩福利| 欧美凹凸一区二区三区视频| 日韩视频不卡中文| 久久久久久久999精品视频| 欧美日韩国产综合视频在线观看| 国产欧美日韩精品丝袜高跟鞋| 亚洲日本成人网| 亚洲欧美日韩精品久久久| 欧美一级片在线播放| 美日韩精品视频免费看| 一区二区欧美亚洲| 久久综合999| 国产日韩综合一区二区性色av| 亚洲福利在线观看| 欧美一区2区三区4区公司二百| 欧美成人首页| 亚洲永久免费视频| 欧美岛国在线观看| 韩国一区二区三区美女美女秀| 亚洲天堂成人| 亚洲国产1区| 久久久久一区二区| 国内精品99| 久久精品国产v日韩v亚洲|