Billboard
Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3119 Accepted Submission(s): 1506
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.
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 "-1" for this announcement.
3 5 5 2 4 3 3 3
1 2 1 3 -1
题目：http://acm.hdu.edu.cn/showproblem.php?pid=2795
题意：这题给出一个h*w的板子，在板子上贴n个1*wi的广告，要求每个广告尽量考上方，在此前提下尽量靠左边，要求输出每个广告在第几行
分析：其实最多就只能用到n行，所以h取h和n的最小值即可，将其转化为h个元素的线段树，表示第i行现在剩下的宽度，线段树维护区间的最大值，每次都查找大于wi的最小行标号就行。。。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int mm=888888;
int val[mm];
int i,n,h,w;
void pushup(int rt)
{
val[rt]=max(val[rt<<1],val[rt<<1|1]);
}
void build(int l,int r,int rt)
{
val[rt]=w;
if(l==r)return;
int m=(l+r)>>1;
build(lson);
build(rson);
}
int updata(int v,int l,int r,int rt)
{
if(l==r)
{
val[rt]-=v;
return l;
}
int m=(l+r)>>1,ret=(val[rt<<1]>=v)?updata(v,lson):updata(v,rson);
if(ret>-1)pushup(rt);
return ret;
}
int main()
{
while(~scanf("%d%d%d",&h,&w,&n))
{
h=min(n,h);
build(1,h,1);
while(n--)
{
scanf("%d",&i);
printf("%d\n",val[1]<i?-1:updata(i,1,h,1));
}
}
return 0;
}