首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。