hdu2795Billboard

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795
单点更新？？
 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define lson l,m,rt<<1
 5 #define rson m+1,r,rt<<1|1
 6 int h,w,n;
 7 const int maxn=200010;
 8 int f[maxn<<2];
 9 
10 void pushup(int rt)
11 {
12     f[rt]=max(f[rt<<1],f[rt<<1|1]);
13 }
14 
15 void build(int l,int r,int rt)
16 {
17     f[rt]=w;
18     if(l==r) return ;
19     int m=(l+r)>>1;
20     build(lson);
21     build(rson);
22 }
23 
24 int query(int x,int l,int r,int rt)
25 {
26     if(l==r)
27     {
28         f[rt]-=x;
29         return l;
30     }
31     int m=(l+r)>>1;
32     int ans=(f[rt<<1]>=x?query(x,lson):query(x,rson));
33     pushup(rt);
34     return ans;
35 }
36 
37 int main()
38 {
39 
40     while(scanf("%d%d%d",&h,&w,&n)!=EOF)
41     {
42         int x;
43         if(h>n) h=n;
44         build(1,h,1);
45         while(n--)
46         {
47             scanf("%d",&x);
48             if(x>f[1]) puts("-1");
49             else printf("%d
",query(x,1,h,1));
50         }
51     }
52 }