線分ツリースペースに格納され、一番上の数(単点更新)
1396 ワード
タイトル:HDU 2795 Billboard
#include <stdio.h>
#define maxn 222222
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int w,h,n;
int MAX[maxn<<2];
int max(int a,int b)
{
return a>b? a:b;
}
void PushUP(int rt)
{
MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void Build(int l,int r,int rt)
{
MAX[rt]=w;
if(l==r)
return;
int m=(l+r)>>1;
Build(lson);
Build(rson);
}
int Query(int x,int l,int r,int rt)
{
if(l==r)
{
MAX[rt]-=x;
return r;
}
int m=(l+r)>>1;
int ret=(MAX[rt<<1]>=x)? Query(x,lson):Query(x,rson);
PushUP(rt);
return ret;
}
int main()
{
while(~scanf("%d%d%d",&h,&w,&n))
{
if(h>n) h=n;
Build(1,h,1);
while(n--)
{
int x;
scanf("%d",&x);
if(MAX[1]<x)
puts("-1");
else
printf("%d
",Query(x,1,h,1));
}
}
return 0;
}