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

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://m.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>
            欧美高清在线视频观看不卡| 亚洲狼人综合| 欧美亚洲网站| 国产日韩在线一区| 久久久久久久久一区二区| 久久成人18免费观看| 尤物网精品视频| 最新日韩精品| 欧美日韩成人在线播放| 亚洲免费视频网站| 午夜精品一区二区三区电影天堂| 国产亚洲女人久久久久毛片| 免费在线观看成人av| 欧美大香线蕉线伊人久久国产精品| 亚洲另类在线一区| 亚洲视频每日更新| 尤物yw午夜国产精品视频明星| 欧美韩日视频| 国产精品久久久久久久午夜| 久久精品亚洲精品| 欧美精品色网| 久久久久9999亚洲精品| 欧美黄免费看| 久久精品欧洲| 欧美日韩一区二区精品| 久久蜜臀精品av| 欧美理论电影在线观看| 久久久久成人精品| 欧美色欧美亚洲高清在线视频| 久久精品国产精品亚洲| 欧美精品在线播放| 噜噜噜躁狠狠躁狠狠精品视频| 欧美另类极品videosbest最新版本| 久久精品成人一区二区三区| 欧美精品123区| 久久男人资源视频| 国产精品久线观看视频| 亚洲国产成人精品女人久久久| 国产精品一区二区在线观看不卡| 欧美韩日亚洲| 在线日本高清免费不卡| 午夜精品一区二区三区在线播放| 亚洲精品影视| 美乳少妇欧美精品| 久久国产精品网站| 国产精品婷婷午夜在线观看| 91久久国产综合久久91精品网站| 伊人久久亚洲热| 校园春色综合网| 香蕉成人啪国产精品视频综合网| 欧美日本三区| 亚洲精品国精品久久99热一| 曰本成人黄色| 久久视频一区二区| 久久人人爽爽爽人久久久| 国产欧美一区二区精品性色| 99国产成+人+综合+亚洲欧美| 亚洲经典自拍| 美女在线一区二区| 欧美激情乱人伦| 亚洲三级免费| 欧美精品国产| 日韩亚洲视频在线| 亚洲视频在线免费观看| 欧美日韩久久精品| av成人福利| 亚洲欧美激情视频在线观看一区二区三区| 欧美激情亚洲另类| 亚洲欧洲另类国产综合| 一本到12不卡视频在线dvd| 欧美精品一区视频| aa亚洲婷婷| 性色av一区二区三区红粉影视| 国产精品久久久久一区二区三区共| 99综合在线| 欧美中在线观看| 一区二区三区在线视频免费观看 | 免费高清在线一区| 在线欧美三区| 欧美欧美全黄| 亚洲一区二区综合| 久久乐国产精品| 最近中文字幕mv在线一区二区三区四区| 六月丁香综合| 99精品久久久| 久久久久久亚洲精品中文字幕| 韩日在线一区| 欧美激情一区在线| 亚洲一区高清| 欧美高清视频一区二区| 亚洲天堂网在线观看| 国产日韩欧美在线观看| 美国十次成人| 在线亚洲欧美视频| 麻豆精品精品国产自在97香蕉| 亚洲激情在线激情| 国产欧美日韩视频一区二区三区 | 99精品视频免费观看视频| 欧美亚洲在线| 亚洲精品日韩欧美| 国产精品自在在线| 欧美精品福利| 久久精品一级爱片| 宅男精品视频| 亚洲第一在线综合在线| 亚洲欧美国产日韩中文字幕| 在线精品国产欧美| 国产精品视频免费| 欧美v国产在线一区二区三区| 日韩视频在线一区二区三区| 久久色在线观看| 亚洲欧美一区二区三区极速播放| 亚洲高清激情| 国产视频精品va久久久久久| 欧美顶级艳妇交换群宴| 久久av一区二区| 一本色道久久综合| 亚洲国产欧美在线人成| 久久久久久久综合色一本| 亚洲一区在线免费| 亚洲最黄网站| 亚洲欧洲视频| 亚洲国产岛国毛片在线| 国产日韩欧美综合一区| 国产精品久久| 欧美日韩精品一区二区三区| 欧美不卡在线| 免费观看日韩| 蜜臀99久久精品久久久久久软件| 香蕉久久久久久久av网站| 亚洲视频网站在线观看| 日韩视频在线观看免费| 亚洲另类自拍| 亚洲精品一区二区在线观看| 亚洲国产成人av| 欧美激情精品久久久六区热门 | 亚洲色在线视频| 99精品久久久| 一区二区三区成人精品| 99精品国产热久久91蜜凸| 日韩小视频在线观看专区| 日韩视频免费| 在线综合视频| 亚洲免费在线播放| 欧美在线观看一区二区三区| 午夜精品国产精品大乳美女| 亚洲欧美色一区| 欧美一级在线播放| 久久精品国产久精国产一老狼| 欧美伊人久久| 久久中文久久字幕| 欧美激情乱人伦| 日韩视频在线你懂得| 亚洲婷婷在线| 欧美一区二区三区在线视频 | 欧美福利视频在线| 欧美日韩精品欧美日韩精品| 欧美四级在线观看| 国产美女精品视频| 影音先锋日韩精品| 亚洲伦理中文字幕| 亚洲欧美日韩另类精品一区二区三区| 性欧美1819性猛交| 欧美va亚洲va香蕉在线| 亚洲精品欧美激情| 亚洲综合精品四区| 久热精品视频在线观看| 欧美日韩午夜精品| 国产视频观看一区| 亚洲日本va午夜在线影院| 亚洲午夜在线| 久久久青草青青国产亚洲免观| 欧美激情小视频| 亚洲午夜小视频| 久久影视三级福利片| 欧美视频中文在线看 | 国产伦精品一区二区三| 亚洲国产精品毛片| 亚洲欧美日韩综合一区| 欧美激情视频网站| 亚洲欧美激情视频| 欧美国产日本| 好吊一区二区三区| 亚洲一区二区三区午夜| 美日韩精品视频免费看| 一区二区欧美亚洲| 免费在线视频一区| 国产一级久久| 亚洲专区在线| 亚洲国产精品一区二区尤物区 | 欧美成人免费视频| 亚洲欧美在线免费观看| 欧美伦理一区二区| 亚洲福利免费| 久久久久青草大香线综合精品| 亚洲理论在线观看| 欧美电影在线观看| 亚洲国产精品久久| 久久久久www| 午夜一区二区三区不卡视频|