首页 > 代码库 > hdu 2795 Billboard

hdu 2795 Billboard

#include<stdio.h>#include<string.h>#include<math.h>#include<iostream>#include<algorithm>#include<queue>#include<stack>#define mem(a,b) memset(a,b,sizeof(a))#define ll __int64#define MAXN 1000#define INF 0x7ffffff#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int h,w,n;struct Tree{    int l,r;    int value,idx;    friend bool operator > (const Tree &a,const Tree &b)    {        if(a.value!=b.value)            return a.value>b.value;        return a.idx<b.idx;    }}sum[1000000];void build(int l,int r,int rt){    sum[rt].l=l;    sum[rt].r=r;    sum[rt].value=w;    sum[rt].idx=l;    if(l==r) return ;    int m=(l+r)>>1;    build(l,m,rt*2);    build(m+1,r,rt*2+1);}int query(int val,int l,int r,int rt){    if(val>sum[rt].value) return -1;    if(l==r)    {        return sum[rt].idx;    }    int m=(l+r)>>1;    if(sum[rt*2].value>=val) return query(val,l,m,rt*2);    else return query(val,m+1,r,rt*2+1);}void update(int l,int r,int val,int rt){    if(l<=sum[rt].l&&sum[rt].r<=r)    {        sum[rt].value-=val;return;    }    int m=(sum[rt].l+sum[rt].r)>>1;    if(l<=m) update(l,r,val,rt*2);    if(r>m) update(l,r,val,rt*2+1);    if(sum[rt*2]>sum[rt*2+1])    {        sum[rt].value=sum[rt*2].value;        sum[rt].idx=sum[rt*2].idx;    }    else    {        sum[rt].value=sum[rt*2+1].value;        sum[rt].idx=sum[rt*2+1].idx;    }}int main(){    int i,j;    int q;    while(scanf("%d%d%d",&h,&w,&n)!=EOF)    {        if(h>n) h=n;        build(1,h,1);        while(n--)        {            scanf("%d",&q);            int temp=query(q,1,h,1);            printf("%d\n",temp);            if(temp!=-1)            {                update(temp,temp,q,1);            }        }    }    return 0;}

 

hdu 2795 Billboard